Как рассчитать сложность времени?

Question

Предположим, что функция f находится в классе сложности O (N (log N)), а для N = 1000 программа запускается за 8 секунд. Как написать формулу T (N), которая может вычислить приблизительное время, которое требуется для запуска f для любого ввода размера N?

Вот ответ:

8 = c (1000 x 10) 
c = 8x10^-4 
T(N) = 8x10-4* (N log2 N) 

Я не понимаю, первая линия, где делает 10 взялось? Может кто-нибудь объяснить мне ответ, пожалуйста? Благодаря!

Answer 1

O (N (log N)^2) описывает, как время выполнения масштабируется с N, но это не формула для расчета времени выполнения в секундах. В самом деле, нотация Big-O обычно не дает точной самой функции масштабирования, но верхняя граница на ней при больших N. См. here (есть хорошая картина, показывающая этот последний пункт).

Если вас интересует время выполнения функции на практике (особенно в неасимптотическом режиме, то есть в малом N), один из вариантов - фактически запустить функцию и измерить ее. Сделайте это для нескольких значений N, выбранных на некоторой сетке (возможно, с нелинейным расстоянием). Затем вы можете интерполировать между этими точками.

Answer 2

Я не понимаю первую строку, откуда поступают 10? Может кто-нибудь объяснит мне ответ, пожалуйста? Благодаря!

T (N) - максимальная временная сложность. c - постоянная или O(1) времени, которая является частью скорости алгоритма, на которую не влияет размер ввода. 10 происходит от округления, чтобы упростить математику. Фактически это 9.965784, что составляет log2 от 1000, т.е.

N x log2 N является
1000 x 10 или
1000 x 9.965784

Answer 3

Определение S(N)=N(log N)^2

Если вы можете предположить, что S (N) ограничивает вашу программу для всех N> = 1000

Тогда вы можете связаны ваши время исполнения по правилу доброй тройки:

S(1000) - T(1000) 
S(N) - T(N) 

T(N) <= S(N)* T(1000)/S(1000) for all N >=1000 

S(1000) approx 10E4 
T(1000) = 8 

T(N) <= N(log N)^2 * 8/10E4