Сложность алгоритма

Question

Какова сложность, заданная для следующей проблемы: O (n). Не должно быть O (n^2)? Это потому, что внешний цикл O (n), а внутренний также O (n), поэтому n * n = O (n^2)?

В листе ответов на этот вопрос указано, что ответ O (n). Как это возможно?

public static void q1d(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n; j++) { 
      count++; 
     } 
    } 
} 

Сложность для следующей проблемы: O (n^2), как вы можете это получить? Может кто-то прокомментировать?

public static void q1E(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n/2; j++) { 
      count++; 
     } 
    } 
} 

Благодаря

Answer 1

Сложность как код О (п * п)

ПЕРВЫЙ

Внешний контур работает n раз, а внутренний цикл изменяется от 0 to n-1 раза

so

total = 1 + 2 + 3 + 4 ... + n

, который, если вы добавите arithmetic progression является n * (n + 1)/2 является O(n*n)

ВТОРОЙ

Внешний цикл проходит n раз, а внутренний цикл колеблется от 0 to n-1/2 времен

так

total = 1 + 1/2 + 3/2 + 4/2 ... + n/2

, который, если вы добавите арифметическую прогрессию является n * (n + 1)/4 также O(n*n)

Answer 2

Первый пример O(n^2), так что кажется, что они совершили ошибку. Чтобы рассчитать (неофициально) второй пример, мы можем сделать n * (n/2) = (n^2)/2 = O(n^2). Если это не имеет смысла, вам нужно пойти и освежить то, что означает что-то, что есть O(n^k).

Answer 3

Первый случай определенно O(n^2)

Второй O(n^2), а потому что вы опускаете константы, когда вычисления большой O

Answer 4

Ваш ответ лист не так, первый алгоритм, очевидно, O (N^2).

Знак Big-Oh «наихудший случай», поэтому при вычислении значения Big-Oh мы обычно игнорируем умножения/деления на константы.

При этом ваш второй пример также является O (n^2) в худшем случае, поскольку, хотя внутренний цикл является «единственным» 1/2 n, n является четким ограничивающим фактором. На практике второй алгоритм будет меньше операций O (n^2), но Big-Oh предназначен для измерения «наихудшего случая» (т. Е. Максимального ограничения), поэтому точное число операций игнорируется в пользу сосредоточив внимание на том, как работает алгоритм, когда n приближается к бесконечности.

Answer 5

Оба являются O(n^2). Ваш ответ неправильный. Или вы можете написать вопрос неправильно.