Сайт Романа ПарпалакаБлог20210301

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

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

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

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

1 марта 2021 года, 22:31     работа программиста

Визуальная конструкция элементов интерфейса Ctrl Анализ данных — В кресле препода №7

Поделиться

Комментарии

#1. 2 марта 2021 года, 10:58. Евгений Степанищев пишет:
Наилучшая сортировка по какому критерию? Если по алгоритмической сложности, то там O(n).
#2. 2 марта 2021 года, 11:37. пишет:
Когда кандидат задает вопрос о критерии, я отвечаю: «По количеству операций с произвольным массивом чисел». O(n) на произвольных входных данных не получится сделать.
Записи