Сайт Романа ПарпалакаБлог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) на произвольных входных данных не получится сделать.

Оставьте свой комментарий

Ваше имя:

Комментарий:

Для выделения используйте следующий код: [i]курсив[/i], [b]жирный[/b].
Цитату оформляйте так: [q = имя автора]цитата[/q] или [q]еще цитата[/q].
Ссылку начните с http://. Других команд или HTML-тегов здесь нет.

Сколько будет 74+9?

Записи