Заметки:
- О-большое описывает скорость работы алгоритмы.
- Время выполнения для бинарного и простого поиска растет с разной скоростью.
- С увеличением списка бинарный поиск занимает чуть больше времени, а простой поиск займет ГОРАЗДО больше времени. В общем, чем больше элементов в списке, тем быстрее работает бинарный поиск по сравнению с обычным поиском.
- О-большое не сообщает скорость в секундах, а позволяет сравнить количество операций. Оно показывает, насколько быстро возрастает время выполнения алгоритма.
- Скорость работы алгоритма обычно описывается как О(n), где n — количество операций. Скорость работы простого алгоритма так и выглядит. Например, если перебираем 100 элементов, то будет О(100).
- Скорость бинарного поиска — О(log n).
- О-большое всегда описывает худший возможный случай. Это позволяет знать, что алгоритм никогда не будет работать медленнее, чем О-большое.
- Существует задача о коммивояжере с худшей скоростью. Коммивояжеру нужно объехать 5 городов в рандомных местах. Надо определить, в каком порядке лучше это сделать. Одно из известных решений — перебрать все возможные комбинации, суммируя расстояния, а потом уже выбрать самый короткий. Но для 5 городов это будет аж 120 вариантов. Для 6 городов уже 730. А для 7 — 5040. Цифры ужасающе быстро растут. Скорость тут O(n!) — факториальная.
Первая часть: https://zen.yandex.ru/media/android_junior/6127f4e93e355f506aa43cf7
