Определение сложности времени и пространства для вложенного цикла с одним постоянным множителем

Question

for 1 to n
 for j=1 to 3
    for i=j to n
       count++

Мой ответ: O (n ^ 2)

Пожалуйста, поправьте меня, если я ошибаюсь. Спасибо

edit: Внутренний цикл работает как для O (n), так и для самого внешнего цикла. Но как насчет j = от 1 до 3?

edit 2: Из того, что я узнал, сложность пространства можно рассчитать, если есть -

• Объявление переменных
• Структуры данных
• Отчисления
• вызов функции

Но в вышеприведенном коде нет ни одного из них. Так какова будет космическая сложность?

Answer 1

Другой способ подойти к этому - переписать код следующим образом:

for x= 1 to n
    for i = 1 to n
        count++
    for i = 2 to n
        count++
    for i = 3 to n    // considering 1 to 3 => [1, 3]
        count++

Тогда мы можем утверждать, что временная сложность всех внутренних циклов равна O(n), то есть O(n) + O(n) + O(n) = O(n).

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

Кроме того, Пространственная сложность равна O(1), поскольку существует только несколько объявлений переменных (объявлены следующие переменные: count, i, j; также вы забыли объявить переменную в самом внешнем цикле), что не зависит от какого-либо внешнего параметра, т. е. сложность пространства остается неизменной независимо от размера ввода.

Answer 2

Это O (n ^ 2), потому что:

• для 1 - это O (n)
• для 2 - O (1) - конечное число действий
• для 3 - это O (n) - i-> n по-прежнему равно O (n), потому что порядок зависит от n

Подводя итог - O (n ^ 2).