временная сложность алгоритма

Question

Алгоритм с размером n = 100 занимает 21 секунду.При размере n = 1000 это занимает 31 секунду, а при n = 10000 - 41 секунда.Какова сложность бега?

Если я попробую O (n), тогда: T (n) = (21 * 1000) / 100 = 210 с (не O (n))
Если я попытаюсь O(n ^ 2) Тогда: T (n) = (21 * 1000 ^ 2) / 100 ^ 2 = 2100 с (не O (n ^ 2))
Если я попробую O (log n), тогда: T (n) = (21 * log1000) /log100=31.5 (не O (log n))

Другой вариант, который мне дан, - O (1 / n).Как рассчитать это?

Answer 1

выглядит как O(lgn).

Время для n равно T(n) = 10*log(n) + 1, когда основание журнала равно 10.

Answer 2

Чтобы решить эту проблему, начните с построения некоторых функций из различных классов.Например, чтобы узнать о линейном классе O(n) функция T(n)=n и узнать о классовом графике O(n^2) функция T(n)=n^2.Это поможет вам распознать форму различных функций.

После этого нарисуйте точки, заданные в ваших вопросах, со значениями n на оси x и временными значениями на оси y.Вы должны быть в состоянии быстро распознать форму в этом вопросе.

Подсказка: это не O(log n): -)