Алгоритмическая сложность

Одна из тем, которые я обязательно поднимаю на собеседовании, — это сложность алгоритмов. Кандидату на мои вакансии достаточно назвать сложность наилучшей сортировки — O(n·ln n). Еще о структурах данных речь заходит при обсуждении работы индексов БД. Кандидат должен объяснить, за счет чего индексы ускоряют выполнение запросов.

Если кандидат не дает ответа O(n·ln n), это тревожный звоночек. В зависимости от вакансии я могу еще попросить оценить сложность простейшей сортировки, например, пузырьком, чтобы отличить пробел в знаниях от неспособности понимать эту тему.

Почему важно иметь представление об алгоритмической сложности? Что будет, если писать код без этого представления? Недавно нашелся пример: если на рабочем столе создать 1000 файлов, Windows тратит 20 секунд на открытие главного меню. И всё потому, что какой-то криворукий программист написал алгоритм сложности O(n²) там, где можно было обойтись O(n). Подробности читайте на хабре.