1. Какие критерии используются для оценки качества алгоритмов?
Основными критериями являются скорость выполнения (количество операций, зависящее от объёма данных), использование памяти (объём ресурсов, необходимых алгоритму), и корректность (получение верного результата для любых входных данных).
2. Почему скорость работы алгоритма оценивается не временем выполнения, а количеством элементарных операций?
Время выполнения зависит от мощности конкретного компьютера, тогда как количество операций показывает универсальную сложность алгоритма, позволяя сравнивать их независимо от аппаратуры.
3. Как учитывается размер данных при оценке скорости алгоритма?
Размер данных обозначают буквой n. Количество операций записывают как функцию от n, чтобы показать, как скорость алгоритма изменяется при увеличении объёма данных.
4. Что означают записи O(1), O(n), O(n^2) и O(2^n)?
O(1): Алгоритм выполняется за постоянное время, независимо от объёма данных. O(n): Время выполнения растёт прямо пропорционально объёму данных. O(n^2): Время выполнения увеличивается пропорционально квадрату объёма данных. O(2^n): Время выполнения растёт экспоненциально, удваиваясь при каждом увеличении данных.
5. В каких случаях алгоритм, имеющий асимптотическую сложность O(n^2), может работать быстрее, чем алгоритм с асимптотической сложностью O(n) ?
Если данных немного, алгоритм с O(n^2) может работать быстрее из-за меньшего числа операций в конкретных случаях. Например, если у него небольшие дополнительные накладные расходы по сравнению с O(n).