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

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

Если я попробую O (n) Тогда: T (n) = (21 * 1000)/100 = 210 с (не O (n))
Если я попробую O (n^2) 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). Как это рассчитать?

источник

2011-02-03 Maria

* Подробнее * Big O домашнее задание Maria/Annita? –

да, как вы можете видеть, я пытался его решить, но не могу найти, как рассчитать O (1/n). Вы можете помочь? – Maria

Может быть полезно: http://www.perlmonks.org/?node_id=94000 –

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

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

источник

2011-02-03 14:40:33

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

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

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

источник

2011-02-03 14:51:19 vidstige

do u думаю, O (n)? Граф линейный. Но когда я использую формулу, я получаю: T (n) = (21 * 1000)/100 = 210 с не 31 с. – Maria

@Maria Да, я думаю, что это так. С помощью только данных синхронизации вы никогда не сможете быть уверенными, но это лучшее, что у нас есть. Помня, что константы «не учитываются» при использовании большой записи O и что линейная эвгация может иметь форму «y = kx + m», т. Е. Для алгоритма, ограниченного константой, может быть «начальная стоимость». Ваши вычисления предполагают, что T (0) = 0, что не всегда верно. Ты видишь? Проверьте график снова. Линия не обрезает ось y на ори. – vidstige

ответ

Смежные вопросы