Какова временная сложность?

Какова временная сложность следующей функции?

    for(int i = 0; i < a.size; i++) {
        for(int j = i; j < a.size; i++) {
            //
        }
    }

Я думаю, что это меньше, чем большой O n ^ 2, потому что мы не перебираем все элементы во втором цикле for. Я считаю, что временная сложность получается примерно такой:

n[ (n) + (n-1) + (n-2) + ... + (n-n) ]

Но когда я решаю эту формулу, получается

n^2 - n + n^2 - 2n + n^2 - 3n + ... + n^2 - n^2

Что совсем не кажется правильным. Может ли кто-нибудь сказать мне, как именно решить эту проблему, и где я ошибаюсь.


algorithm time-complexity big-o runtime-compilation
person user2158382    schedule 13.05.2014    source источник
comment
Внешний n неверен, так как вы уже перечислили все элементы. Кроме того, внутренний цикл идет от i к n-1, а не от i+1 к n-1, поэтому для первой внешней итерации это n, а не n-1.   -  person Gumbo    schedule 13.05.2014
comment
Почему мне не нужен внешний цикл? Разве внутренний цикл j не будет выполняться для каждого внешнего цикла i?   -  person user2158382    schedule 13.05.2014
comment
@ user2158382, он не предполагает, что вам не нужен другой цикл. Он говорит, что ваше вычисление временной сложности не должно иметь внешнего n.   -  person merlin2011    schedule 13.05.2014

Ответы (3)


arrow_upward
5
arrow_downward

Это O(n^2). Если вы рассматриваете итерацию, где i = a.size() - 1, и работаете в обратном направлении (i = a.size() - 2, i = a.size - 3 и т. д.), вы смотрите на следующую сумму количества итераций, где n = a.size.

1 + 2 + 3 + 4 + ... + n

Сумма этого ряда равна n(n+1)/2, что равно O(n^2). Обратите внимание, что нотация big-O игнорирует константы и принимает наивысшую полиномиальную степень, когда она применяется к полиномиальной функции.

person merlin2011    schedule 13.05.2014
comment
Я не понимаю, как циклы работают для 1 + 2 + 3 + 4 + ... + n. Я полагаю, что это будет работать для 1 + 2 + 3 + 4 + ... + n для каждой итерации i? Потому что для каждой итерации i будет запускаться j 1 + 2 + 3 + 4 + ... + n. - person user2158382; 13.05.2014
comment
@user2158382 user2158382, поскольку вы не сказали нам, что находится внутри внутреннего цикла, все ответы, которые мы здесь написали, предполагают, что операция внутри внутреннего цикла занимает постоянное время, и поэтому мы просто подсчитываем число повторений внутреннего цикла работает. Как я уже упоминал в ответе, рассмотрим, что происходит на итерации i = a.size() - 1. В этой итерации внутренний цикл будет выполняться ровно один раз. На итерации i = a.size() - 2 внутренний цикл будет выполняться ровно дважды. - person merlin2011; 13.05.2014

arrow_upward
2
arrow_downward

Он будет работать для:

1 + 2 + 3 + .. + n

Что 1/2 n(n+1) дает нам O(n^2)

Обозначение Big-O будет сохранять только доминирующий член, пренебрегая константами.

Big-O используется только для сравнения алгоритмов на одном и том же варианте задачи с использованием одного и того же стандарта анализа сложности, если и только если доминирующие условия различаются.

Если доминирующие термины одинаковы, вам необходимо сравнить сложность Big-Theta или Time, которая покажет незначительные различия.

введите здесь описание изображения

Пример

A

    for i = 1 .. n
      for j = i .. n
        ..

B

    for i = 1 .. n
      for j = 1 .. n
        ..

У нас есть

Time(A) = 1/2 n(n+1) ~ O(n^2)

Time(B) = n^2 ~ O(n^2)

O(A) = O(B)

T(A) < T(B)

Анализ

Чтобы представить, как мы получили 1 + 2 + 3 + .. n:

    for i = 1 .. n:
      print "(1 + "
      sum = 0
      for j = i .. n:
        sum++
      print sum") + "

напечатает следующее:

(1+n) + (1+(n-1)) + .. + (1+3) + (1+2) + (1+1) + (1+0)

n+1 + n + n-1 + .. + 3 + 2 + 1

1 + 2 + 3 + .. + n + n+1

1/2 n(n+1) + (n+1)

1/2 n^2 + 1/2 n + n + 1

1/2 n^2 + 3/2 n + 1
person Khaled.K    schedule 13.05.2014
comment
Не могли бы вы объяснить, почему сериал идет 1 + 2 + 3 + .. + n? - person user2158382; 13.05.2014
comment
Разве серия не будет выполняться для n*(1 + 2 + 3 + 4 + ... + n), потому что для каждой итерации i j должно запускаться из 1 + 2 + 3 + 4 + ... + n - person user2158382; 13.05.2014
comment
@user2158382 user2158382 проверь конец ответа - person Khaled.K; 13.05.2014

arrow_upward
1
arrow_downward

Да, количество итераций строго меньше n^2, но все равно Θ(n^2). В конечном итоге оно будет больше n^k для любого k<2 и в конечном итоге станет меньше n^k для любого k>2.

(Кстати, ученые-компьютерщики часто говорят «большой-0», когда на самом деле имеют в виду «большой тета» (Θ). Технически правильно сказать, что почти каждый алгоритм, который вы видели, имеет O(n!) времени выполнения; все разумные алгоритмы имеют время выполнения, которое растет. не быстрее, чем n!. Но на самом деле бесполезно говорить, что сложность равна O(n!), если она тоже O(n log n), поэтому в соответствии с какой-то максимой Грайса мы предполагаем, что когда кто-то говорит сложность алгоритма равна O(f(x)), что f(x) как можно меньше.)

person hobbs    schedule 13.05.2014