История изменений
Исправление KivApple, (текущая версия) :
Как бы нормальные люди смотрят на сложность всех алгоритмов, которые использует программа.
И если на входе не отсортированные данные, то сложность поиска будет O(сложность сортировки + сложность двоичного поиска). И в таком случае можно будет сделать вывод, что тупой перебор ничуть не хуже. Зато если данные уже отсортированы, то двоичный поиск будет очень кстати. Или если искать надо часто, то сложность тупого перебора будет O(количество элементов * количество поисков). А сложность двоичного поиска (сложность сортировки + сложность двоичного поиска * количество поисков). И тут можно нехитрыми вычислениями определить, что после определённого количества поисков будет выгоднее сначала отсортировать массив, а уже потом искать в нём что-либо.
Оценка сложности это инструмент и им надо уметь пользоваться. И оценивать надо сложность всех частей алгоритма, а не вырывать информацию из контекста.
И да, каким бы ты не был крутым программистом, но одинаково оптимизированный алгоритм O(1) в 99.9% случаев будет жёстко уделывать алгоритм O(N). И никакой крутой реализацией ты это не изменишь.
Поэтому логично сначала оценить сложности алгоритмов и выбрать лучший, а уже потом написать оптимальную реализацию этого алгоритма. Чем выбрать произвольный алгоритм, оптимизировать его и упереться в предел оптимизации не достигнув нужной производительности, а потом переписывать код с нуля.
Исходная версия KivApple, :
Как бы нормальные люди смотрят на сложность всех алгоритмов, которые использует программа.
И если на входе не отсортированные данные, то сложность поиска будет O(сложность сортировки + сложность двоичного поиска). И в таком случае можно будет сделать вывод, что тупой перебор ничуть не хуже. Зато если данные уже отсортированы, то двоичный поиск будет очень кстати. Или если искать надо часто, то сложность тупого перебора будет O(количество элементов * количество поисков). А сложность двоичного поиска (сложность сортировки + N * сложность двоичного поиска * количество поисков). И тут можно нехитрыми вычислениями определить, что после определённого количества поисков будет выгоднее сначала отсортировать массив, а уже потом искать в нём что-либо.
Оценка сложности это инструмент и им надо уметь пользоваться. И оценивать надо сложность всех частей алгоритма, а не вырывать информацию из контекста.
И да, каким бы ты не был крутым программистом, но одинаково оптимизированный алгоритм O(1) в 99.9% случаев будет жёстко уделывать алгоритм O(N). И никакой крутой реализацией ты это не изменишь.
Поэтому логично сначала оценить сложности алгоритмов и выбрать лучший, а уже потом написать оптимальную реализацию этого алгоритма. Чем выбрать произвольный алгоритм, оптимизировать его и упереться в предел оптимизации не достигнув нужной производительности, а потом переписывать код с нуля.