Объясните, почему утверждение «Время выполнения алгоритма A не меньше O(n^2)» бессмысленно.

Question

Объясните, почему утверждение «Время выполнения алгоритма A не меньше O(n^2)» бессмысленно.

Anastasia Soft Знаток (359), закрыт 5 лет назад

Речь идет про большую О

Answer 1

Потому, что O - это НЕ время выполнения, а ЗАВИСИМОСТЬ объёма вычислений от объёма обрабатываемых данных. При этом алгоритм O(n) может потребовать 100*n операций, а O(n^2) - 2*n^2 операций. И для сортировки 10 элементов пузырёк O(n^2) будет быстрее любого "быстрого" алгоритма с O(n*log(n)).

Answer 2

Может, потому как должно оцениваться худшее возможное время алгоритма? https://en.wikipedia.org/wiki/Worst-case_complexity

Answer 3

неясно куда копать - с одной стороны о большое это не время выполнения алгоритма, с другой - возможно вам дан какой то конкретный алгоритм А, с третьей - как правило оценивают среднее и худшее значение о большого, минимальное просто не нужно