Основные алгоритмы книга, уточнение требуется

Question

Integer: FindMedian(Integer: array[]) 
For i = 0 To array.Length - 1 
// Find the number of values greater than and less than array[i]. 

Integer: num_larger = 0 
Integer: num_smaller = 0 

For j = 0 To array.Length - 1 
    If (array[j] < array[i]) 
     Then num_smaller = num_smaller + 1 
    If (array[j] > array[i]) 
     Then num_larger = num_larger + 1 Next j 
    If (num_smaller = num_larger) 
     Then Return array[i] 
    End If 
Next i 
End FindMedian 

Теперь о сложности алгоритма: автор говорит:

Если массив содержит N значений, внешняя Для КОНТУРА выполняется N раз. Для каждой из этих итераций внутренний цикл For j выполняет N раз. Это означает, что шаги внутри внутреннего цикла выполняют N × N = N раз, предоставляя алгоритму время выполнения O (N).

Я думаю, что сложность должна быть O (N^2). Я ошибаюсь?

Answer 1

Конечно, порядок будет o (N^2), потому что для каждого внешнего цикла ваш внутренний цикл будет работать n раз, так что существует n внешняя петля. сложность времени будет o (n^2).

Не могли бы вы поделиться ссылкой на книгу с номером страницы, на которой вы ее нашли?

Answer 2

Да, я думаю, что это так.

От https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

O(N^2) представляет собой алгоритм, производительность прямо пропорциональна квадрату размера набора входных данных. Это часто встречается с алгоритмами, которые связаны с вложенными итерациями над набором данных. Более глубокая вложенная итерация приведет к O(N^3), O(N^4) и т.д.

bool ContainsDuplicates(IList<string> elements) 
{ 
    for (var outer = 0; outer < elements.Count; outer++) 
    { 
     for (var inner = 0; inner < elements.Count; inner++) 
     { 
      // Don't compare with self 
      if (outer == inner) continue; 

      if (elements[outer] == elements[inner]) return true; 
     } 
    } 

    return false; 
} 

Какого именно то, что вы просите.