В программировании есть концепция сложности алгоритмов. Она показывает, сколько операций потребуется в наихудшем случае для достижения результата. Принятое обозначение O() [о большое]
Сравнивая сложность двух алгоритмов, можно выбрать наиболее подходящий для конкретной задачи.
Давайте рассмотрим пример простого поиска перебором:
def simple_search(digit_list: list[int], need_digit: int) -> tuple[int | None, int]:
"""
Простой поиск вхождения числа перебором. Если значения нет -None
:param digit_list: список чисел для поиска
:type digit_list: list[int]
:param need_digit: искомое число
:type need_digit: int
:return: индекс элемента (None - если нет) и количество итераций
:rtype: tuple[int | None, int]
"""
iteration: int = 0
for index, digit in enumerate(digit_list):
iteration = iteration + 1
if digit == need_digit:
return index, iteration
return None, iteration
example_digit_list: list[int] = list(range(0, 1000))
if __name__ == '__main__':
print(simple_search(example_digit_list, 999)) # Индекс - 999, итераций - 1000
print(simple_search(example_digit_list, 0)) # Индекс - 0, итераций - 1
Более читаемая версия - https://t.me/john_soi_blog/15
Данный алгоритм очень эффективен, если искомый элемент находится в начале, но очень плох - если он находится в конце (так мы перебираем все элементы списка). Если передать 1 000 000 записей - иы переберем все. То есть для списка с n записями нужно n итераций (шагов). Значит сложность алгоритма - O(n).
В следующий раз мы рассмотрим бинарный поиск и сравним его с простым. Превью - я покажу как угадать число от 1 до 100 за 7 шагов.
Подписывайтесь на канал, чтобы получать больше полезных советов для программистов:
В телеграмм - https://t.me/john_soi_blog
В дзене - https://dzen.ru/john_soi_blog