Big-O Notation

1. Скорость алгоритмов не измеряется в секундах.
2. Время выполнения алгоритма описывается ростом количества операций.
3. Время выполнения алгоритмов выражается как "Big-O / О-большое".

Диаграмма сложности Big-O

Big-O Complexity Chart. Источник: www.bigonotation.net

1. O(log n), или логарифмическое время. Пример: бинарный поиск.
2. O(n), или линейное время. Пример: простой поиск.
3. O(n * log n). Пример: эффективные алгоритмы (быстрая сортировка).
4. O(n²). Пример: медленные алгоритмы сортировки (сортировка выбором).
5. O(n!). Пример: очень медленные алгоритмы (задача о коммивояжёре).

Типовые операции со структурами данных

Common Data Structure Operations. Источник: www.bigonotation.net

Алгоритмы сортировки массивов

Array Sorting Algorithms. Источник: www.bigonotation.net