Вычислительная сложность алгоритма вложенного

Question

Дан массив а [1,2,3,4,5,6,7,8,9,10], скажем, у нас есть алгоритм, который делает следующее:

for i in 0..a.length 
    for j in 0..a.length 
    ... 

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

Но что, если внутренний контур прошел только от внешнего указателя вперед?

for i in 0..a.length 
    for j in i..a.length 
    ... 

То есть, в сравнении, первый алго будет смотреть на n элементов на каждой итерации (внешняя петля). Второй алго смотрит на:

• п элементов на первой итерации
• п-1 элементов на второй итерации
• п-2 элементы на третьей итерации
• ...
• 1 элемент на последней итерации

При расчете времени выполнения Big O для этого вида алгоритма, все равно O (n^2)?

Answer 1

Это еще O (n^2). Сумма 1 + 2 + ... + n равна n (n + 1)/2, что равно O (n^2).

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

Answer 2

Если вам дано, что a - это конкретный массив, то временная сложность для этого алгоритма постоянна (или O (1)). Может быть, я читал то, что вы просили слишком буквально, но для того, чтобы быть максимально жесткой O (n^2), a должен быть массивом типа [1,2, ..., n]. Если a явно имеет размер 10, тогда алгоритм всегда работает с одинаковым числом шагов.

Надеюсь, этот ответ не нужен, но я преподаватель для дискретного математического класса, и мы часто задаем вопросы об уловке, которые очень похожи на это. Если я неправильно понял вопрос, тогда я приношу извинения за то, что тратил ваше время! Кроме того, ответ, который уже был опубликован, очень хорош!