Я когда-то это понимал, но не больше. Допустим, у меня есть алгоритм, который вернет число в середине массива.Сложность времени работы O (n/2)
for (int i = 0; i < nums.length; i++) {
if (i == nums.length/2) return nums[i];
}
Худший случай от этого всегда будет O (n/2) вправо? Здесь нет худшего случая. Но почему мы просто заключаем, что это O (n)?
Сложность времени O не связана с измерением времени, в течение которого будет выполняться алгоритм, вместо этого он определяет, какие переменные зависят от временной сложности и какова связь между этими переменными и временной сложностью (то есть линейной, полиномиальной , экспоненциальный и т. д.).
Поскольку константы не влияют на тип функции, временная сложность заключается в том, что они не изменяют значение Big O.
Обратите внимание, что в вашем случае код, который вы написали, может фактически скомпилировать что-то с постоянным временем, если компилятор достаточно умен, чтобы заметить, что все итерации цикла мертвы, но один.
Привет, если у меня есть еще один алгоритм, который обрабатывает весь массив вместо половины. Таким образом, они оба O (n). Но когда люди хотят узнать, какой из них быстрее, они собираются сказать, что это но на самом деле тот, который в два раза меньше, чем в два раза быстрее! – Zanko
@Zanko Это правда, однако Big O не является инструментом для этой работы. Я не знаю, как обозначить то, что вы ищете не то, что это означает, что это не существует, просто я не знаю об этом). Я бы просто использовал несколько слов, чтобы описать, что он в два раза быстрее, чем другой – Vality
@ Zanko, зная, какой алгоритм быстрее * не * O полезен - он предназначен для прогнозирования того, как алгоритм реагирует на вход различного размера ! Нередко найти алгоритмы с более высоким 'O()', которые быстрее выполняются на маленьком 'n'. –
Для целей 'O (...)' константы не имеют значения. Это все о том, как увеличивается время *, поскольку количество элементов увеличивается, а не абсолютное значение времени. –
'2' - некоторый постоянный коэффициент, поэтому' O (n/2) 'можно уменьшить до' O (n) '. Другими словами, сложность рассмотрения половины элементов не хуже, чем просмотр всех элементов. –
Меня беспокоит то, что O (n/2) сводится к O (n). Что делать, если код написан вместо 'if (i == nums.length/2) return nums [i];' we have 'if (i == nums.length/999999999) return nums [i];' then it всегда будет первым элементом. Итак, (O (n/99999999) технически O (1)? – Zanko