Эффективность в реализации алгоритма

Что означает "Алгоритм должен быть формой бинарного поиска эффективности" точно означает? Я написал код домашней работы для алгоритма так, как его просили, но в конце концов, одно предложение требует, чтобы алгоритм был формой бинарного поиска эффективности... Означает ли это, что сложность равна бинарный поиск?

2 ответа

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

Algorithm needs to be what? form of binary search
For what purpose? for efficiency


Да, это означает, что сложность сравнима с сложностью двоичного поиска, т.е. O (lg (n)). В основном это означает, что вы должны сделать что-то, что уменьшает вычисление до половины его исходного состояния на каждом шаге. Итак, если 1 - это количество вычислений, требуемое на начальном этапе, тогда 1 становится равным 1/2, затем 1/4, а затем 1/8 и т.д. С каждым шагом.

licensed under cc by-sa 3.0 with attribution.