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

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

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

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

редактировать: самый внутренний цикл выполняется для O (n), а также самый внешний цикл. А как насчет j=1 to 3 ?

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

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

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


algorithm time-complexity big-o space-complexity
person tuhi009    schedule 01.05.2018    source источник
comment
Возможный дубликат Big O для 3 вложенных циклов   -  person Lasitha Petthawadu    schedule 01.05.2018
comment
Вы правы, поскольку вторая строка является постоянным фактором и не влияет на сложность большого O.   -  person silleknarf    schedule 01.05.2018
comment
спасибо @silleknarf за ответ.   -  person tuhi009    schedule 01.05.2018
comment
Да. Ты прав. Сложность точно равна (3*n*(n+1))/2, а в мире сложности это O(n^2).   -  person AliJP    schedule 01.05.2018
comment
@AliJP На самом деле это n(3n-2), потому что j в третьем цикле исходит из второго цикла, а не из первого.   -  person Holt    schedule 01.05.2018
comment
Привет и добро пожаловать в с-о! Непонятно, в чем именно заключается ваш вопрос: как рассчитать сложность? У вас есть конкретный вопрос о вычислениях в этом примере? Просто дать свой ответ (без работы) и спросить, верен ли он, не является хорошим вопросом, потому что неясно, в чем заключается ваша конкретная проблема (кроме, предположительно, правильной домашней работы).   -  person Paul Hankin    schedule 01.05.2018
comment
@PaulHankin да. Как я уже сказал в отредактированном разделе, я не знаю, как рассчитать 2-й цикл.   -  person tuhi009    schedule 01.05.2018
comment
Я добавил свои мысли о космической сложности. Может ли кто-нибудь помочь мне и там? Спасибо   -  person tuhi009    schedule 02.05.2018

Ответы (2)


arrow_upward
1
arrow_downward

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

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

суммировать - O(n^2).

person idan    schedule 01.05.2018
comment
Я добавил свои мысли о космической сложности. Можете ли вы помочь мне и там? Спасибо - person tuhi009; 02.05.2018

arrow_upward
1
arrow_downward

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

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; также вы забыли объявить переменную в самом внешнем цикле), которые не зависят ни от каких внешних параметров, т.е. Сложность пространства остается неизменной независимо от размера ввода.

person Shubham    schedule 02.05.2018