Биг-О обозначение 1 + 2 + 3 + ... + n

Question

В настоящее время я учусь на старшекурсника CS в курсе структур данных.В течение семестра мы узнали о нотации big-O, и в одном задании нам пришлось выписать нотацию big-O суммирования чисел 1 + 2 + 3 + ... + n.Я подумал, что в простейшем методе вы будете циклически переходить от 1 к n, и на каждой итерации добавляете i к сумме, так что казалось, что это будет O (n) время.

Я тожесознавая, что это конкретное суммирование может быть выражено как (n (n + 1)) / 2 как более прямой способ получить ответ.

Мой профессор настаивает на том, что в обоих случаях временная сложность равна O (n^ 2), и я переписывался с ним по электронной почте в надежде получить лучшее объяснение, но он в основном посылает один и тот же ответ каждый раз.

Я чувствую, что, должно быть, неправильно понимаю цель «большого» впервое место.Даже когда я реализую эти 2 метода нахождения суммы в программе и времени выполнения, время метода цикла, по-видимому, линейно увеличивается в зависимости от размера n, а во втором методе это занимает столько же времени, скольконезависимо от того, насколько велико n, потому что в этом случае не происходит итераций.

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

Answer 1

Вы вычисляете порядок неправильного значения.

Как вы указали в комментарии, вопрос не задает, какова временная сложность выполнения суммы;вопрос спрашивает, каков порядок самой суммы .И действительно, 1 + 2 + ... + n - это O (n²).

Answer 2

В примере Java, подобном этому

int n = 1000;
int sum = 0;

// iterating n times
for (int i = 1; i <= n; i++) {
    // just a basic operation, so no extra complexity here
    sum += i;
}

сложение вызывается n раз, поэтому весь код имеет временную сложность O (1) * n = O (n).

Если в вашем вопросе ничего не пропущено, O (n) будет правильным ответом на задание.

В любом случае, есть хорошийшанс, что профессор прав; -)

O (n * (n + 1) / 2) = O (n / 2) * O ((n + 1) / 2) = O (n) * O (n + 1) = O (n) * O (n) = O (n * n) = O (n ^ 2)

Answer 3

Ответ - O (n), если вы делаете суммирование, перебирая числа по одному.

Ответ - O (1), если вы используете формулу для суммирования напрямую.

Answer 4

Возможно ли, что это недоразумение и что 1, 2, ..., n являются временными значениями другой выполняемой операции, что означает, что время для выполнения этой операции постоянно увеличивается, и вы должны дать Большой-O для этой последовательности операций?

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