0
int binsearch(int list[], int searchnum, int left, int right) {

    int middle;
    while (left <= right) {
        middle = (left + right) / 2;
        if (list[middle] < searchnum) {
            left = middle + 1;
        }
        else if (list[middle] == searchnum) {
            return middle;
        }
        else {
            right = middle - 1;
        }
    }
    return -1;
}

int binSearchRecurse(int list[], int searchnum, int left, int right) {

    int middle;
    while (left < right) {

        middle = (left + right) / 2;
        if (list[middle] < searchnum) {
            binSearchRecurse(list, searchnum, middle + 1, right);
            break;
        }
        else if (list[middle] == searchnum) {
            return middle;
            break;
        }
        else {
            binSearchRecurse(list, searchnum, left, middle - 1);
            break;
        }
    }
}

Это функции.

int seqSearch(int[], int, int);
int main() {

    int i, j, position;
    int list[MAX_SIZE];
    int sizeList[] = {0,10,20,30,40,50,60,70,80,90,100,200,400,600,800,1000};
    int numTimes[] = {30000,12000,6000,5000,4000,4000,4000,3000,3000,2000,2000,1000,500,500,500,200};

    clock_t start, stop;
    double duration, total;

    for (i = 0; i < MAX_SIZE; i++)
        list[i] = i;

    for (i = 0; i < ITERATIONS; i++) {
        start = clock();

        for (j = 0; j < numTimes[i]; j++) {
            position = seqSearch(list, -1, sizeList[i]);
        }
        stop = clock();
        total = ((double)(stop - start));
        duration = total / numTimes[i];
        cout << sizeList[i] << " " << numTimes[i] << " " << (int)(stop - start) << " " << total << " " << duration << endl;
        list[sizeList[i]] = sizeList[i];
    }
    system("pause");
    getchar();
    return 0;
}

int seqSearch(int arr[], int n, int x) {

    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

Через это нужно определить the worst case performance и среднее время бинарного алгоритма. Для меня это новое считать такие вещи, кто может помогите. Спасибо.

1 ответ 1

1

Для бинарного поиска в обоих вариантах производительность в наихудшем случае равна O(log n), для последовательного (seqSearch) - O(n).

Это если вас интересует ответ. Если интересует, как это считать - то возьмите практически любую книжку по алгоритмам. Очень кратко - бинарный поиск делит пополам весь диапазон, так что для длины 2k надо сделать k делений, или для диапазона длиной n - около log n делений. Проверка же выполняется за постоянное время.

У последовательного в наихудшем случае надо перебрать все n элементов.

В наилучшем случае вы и там, и там попадаете на искомый элемент сразу, - итого O(1), в среднем - тоже O(log n) у бинарного, O(n) у последовательного.

3
  • а для чего используется код в main()?
    – arman
    11 апр 2017 в 8:12
  • Как я понимаю, для выполнения хронометража и построения графиков, на практике доказывающих сделанные выводы о производительности алгоритмов.
    – Harry
    11 апр 2017 в 8:28
  • спасибо больщое.
    – arman
    11 апр 2017 в 8:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.