Представление Big-O для простого алгоритма

Question

Как я могу представить его сложность с нотой Big-O? Я немного запутался, так как второй для цикла изменяется в соответствии с индексом внешнего цикла. Все еще O (n^2)? или менее сложно? Заранее спасибо

for (int k = 0; k<arr.length; k++){ 
     for (m = k; m<arr.length; m++){ 
      //do something 
     } 
} 

Answer 1

Ваша оценка исходит из progression формулы:

и, таким образом, является O(n^2). Почему ваш случай прогрессирует? Потому что это n + (n-1) + ... + 1 суммирование для ваших циклов.

Answer 2

Если вы добавите все итерации второго цикла, вы получите 1 + 2 + 3 + ... + n, что равно n (n + 1)/2 (n - длина массива). Это n^2/2 + n/2. Как вы, возможно, уже знаете, соответствующий термин в примечаниях с большими онами - это тот, который имеет самую большую мощность, а коэффициенты не имеют отношения к делу. Итак, ваша сложность по-прежнему равна O (n^2).

Answer 3

также среда выполнение составляет около половины п^2 петли

• , но в больших обозначениях O все равно O (N^2)
• , потому что любой постоянное время/цикл - операция представляются как O (1)
• поэтому O ((n^2)/2) -> O ((n^2)/c) -> O (n^2)
• Неофициально существует много людей, использующих O ((n^2)/2) включая меня для собственных целей (более интуитивно понятный и сопоставимый) ... ближе к циклу/времени выполнения

надеюсь, что это поможет