ВРЕМЯ ВЫПОЛНЕНИЯ АЛГОРИТМА
O(log n) (Логарифмическое)
Каждый раз размер области поиска уменьшается вдвое, поэтому количество операций,
которые нужно сделать, - это степень, в которой 2 равна n.
Представим, что мы уже нашли единственный искомый элемент и пройдем путь поиска
в другую сторону. Увеличим количество в два раза, потом еще в два раза, и еще -
до тех пор, пока не достигнем n. Это и будет O(log n).
| Элементов | Попыток |
|---|---|
| 128 | 7 |
| 1024 | 10 |
Алгоритмы: бинарный поиск
O(n) (Линейное)
Чтобы точно найти ответ, нужно перебрать все элементы массива,
то есть сделать n операций.
| Элементов | Попыток |
|---|---|
| 100 | 100 |
| 1000 | 1000 |
Алгоритмы: простой поиск
O(n * log n)
Алгоритмы: эффективные алгоритмы сортировки (быстрая сортировка).
O(n2)
Алгоритмы: медленные алгоритмы сортировки (сортировка выбором).
O(n!)
Для получения ответа требуется просмотреть все комбинации всех элементов
(количество перестановок - n!).
Краткое описание задачи о коммивояжере - предположим коммивояжер хочет побывать
в 5 городах так, чтобы при этом проехать минимальное общее расстояние
Одно из возможных решений: нужно перебрать все возможные комбинации порядка
объезда городов, чтобы найти наименьшую длину пути.
Для 5 городов это будет - 120 вариантов, для 6 - 720, для 7 - 5040
| Элементов | Попыток |
|---|---|
| 5 | 120 |
| 7 | 5040 |
Алгоритмы: очень медленные алгоритмы (задача о коммивояжере)
Время выполнения алгоритмов растет с разной скоростью. Чем больше выборка,
тем больше разница между линейным и логарифмическим временем.
Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций.
Нотация O-большое позволяет сравнить время выполнения алгоритмов (в худшем случае).
По сути формула описывает, насколько быстро возрастает время выполнения алгоритма
с увеличением размера входных данных.
БИНАРНЫЙ ПОИСК
Бинарный поиск - алгоритм поиска элемента в отсортированном массиве.
Он делит массив на две части, берет "центральный" элемент, сравнивает его значение
с искомым - и на основании этого сравнения отбрасывает одну из двух частей. Таким образом,
область поиска каждый раз сокращается вдвое.
Важное условие: массив значений должен быть отсортирован.
Время выполнения: логарифмическое - O(log n)
Код бинарного поиска в этой папке