Сложность выполнения Runtime

Question

Каков наилучший способ расчета сложности выполнения для любого метода? Это легко сделать, что для не рекурсивных методов, как BubbleSort

outer-for loop 
{ 
    inner-for loop 
     { 
      compare and exchange 
     } 
} 

Чтобы проверить, лучший способ это поставить счетчик в внутрипартийной большей петле. Но, когда этот метод является рекурсивным, где я должен поставить счетчик, например, сортировка слиянием,

sort(int[] array){ 

    left = first-half 
    right = second-half 

    sort(left); 
    sort(right); 
    ret merge(left, right); 

} 

merge(int[] left, right) 
{ 
    count = length(left + right); 
    int[] result; 
    loop-count-times 
    { 
     compare and put in result; 
    } 

    return result; 
} 

Поскольку это сортировка слиянием, большой (о) о (п § п), так что массив 100 ints должны возвращать большое значение o 200 точно. Куда идет счетчик? Если я положил его в начало сортировки (..), я получаю в среднем 250, 280, 300, что должно быть неправильно. Какое лучшее место для этого счетчика?

ссылки: http://en.wikipedia.org/wiki/Mergesort

Спасибо.

Answer 1

Я думаю, что вы неправильно поняли концепцию нотации Big-O. Если сложность O (n log n), а значение n равно 100, то строгое правило, что программа должна выполняться точно в Big-O 200. Она дает только верхнюю границу. Например, рассмотрите сортировку выбора с сложностью O (n). Даже если n равно 100, счетчик, установленный внутри внутреннего контура, не даст вам 100 в результате, если список уже отсортирован. Таким образом, в вашем случае то, что вы получаете как ответ (250, 280, 300 и т. Д.), Совершенно справедливо. Поскольку все ответы ограничены k раз n log n, где k - произвольная константа.

Answer 2

Так как это сортировка слияния, то большой (o) - это o (n log n), поэтому массив из 100 ints должен возвращать значение big-o of 200 точно.

Даже близко не направо.

Вычислительная сложность, обозначаемая с использованием большой ордо-нотации не, расскажет вам, сколько шагов/вычислительных операций будет выполнено точно. Причина в том, что это называется асимптотический, а не идентичный сложность: он дает только функцию, которая приближается (точнее, дает более высокую оценку) время работы алгоритма относительно размера ввода.

Так O(n log n) не означает, что для 100 элементов, 200 операций будет выполняться (как же, кстати, что основание логарифма должно быть 10?), он говорит вам, что если вы увеличиваете размер вашего ввода, время ожидания (средний случай) будет пропорционально количеству добавленных фрагментов входных данных, умноженное на логарифм числа этих дополнительных данных.

К точке: если вы хотите, чтобы подсчитать количество вызовов рекурсивной функции, вы должны поставить счетчик в качестве аргумента, например:

void merge_sort(int array[], size_t length, int *counter) 
{ 
    (*counter)++; 
    // apply the algorithm to `array`: 
    merge_sort(array, length, counter); 
} 

и назвать его так:

int num_calls = 0; 
merge_sort(array, sizeof(array)/sizeof(array[0]), &num_calls); 
printf("Called %d times\n", num_calls);