Самая большая головоломка, решаемая за одну секунду, если предположить, что она занимает f (n) микросекунд

Question

У меня есть вопрос:

f(n) = log(n) (it's log base 2 btw)

Какой самый большой размер n задачи может быть решен за одну секунду, если предположить, что проблема занимает f (n) микросекунд?

Хорошо, поскольку f (n) - это log (n), проблема занимает log (n) микросекунд, верно?И миллионы микросекунд в секунду, верно?Поэтому я настроил это так:

log(n) = 1000000

Но это дает 2 ^ 1000000 в качестве ответа, и это абсолютно неприятно огромное число.Я что-то не так делаю?

Answer 1

Ваша математика верна.

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

Таким образом, каждый раз, когда вы выбираете ребенка, вы отрезаете половину дерева. В начале у вас есть 2 ^ 1 000 000 узлов. Когда вы переходите к следующему дочернему элементу, у вас вдвое меньше узлов, 2 ^ 999 999. После 1 миллиона операций вы должны оказаться на листе, который содержит искомый узел.

Answer 2

Отлично.O (log (n)) алгоритмы очень быстрые.

Конечно, в реальной жизни f (n) не будет log (n) вечно, если вы работаете с каким-то набором данных, вы 'Недостаточно памяти и начнется удар по диску, который будет медленным, и через некоторое время у вас кончится все дисковое пространство на земле ...