Является ли обозначение Big O вложенного зависимого для цикла всегда n ^ 2

Question

Всегда ли обозначение Big O для вложенных зависимых циклов всегда O (n ^ 2)?

Answer 1

Большая буква O обозначает верхнюю границу. Поэтому для dependent for loop рассмотрим следующий пример:

for(i=0;i<n;i++)
    for(j=0;j<i;j++)

Может быть изменено на:

for(i=0;i<n;i++)
    for(j=0;j<n;j++)

Это означает, что у вас есть два цикла, запущенных n раз, и верхняя граница равна n ^ 2. Отсюда обозначение big-O как O (n ^ 2)

Надеюсь, это поможет!

Answer 2

Нет, не обязательно. Это зависит от алгоритма.

например. семантика «group by» в основном обрабатывает группы во внешнем цикле, в то время как элементы группы обрабатываются во (вложенном) внутреннем цикле. Но в конце дня каждый товар обрабатывается только один раз. С алгоритмом хэшированной группировки это может быть только O (n).

Итак, общий ответ на ваш вопрос: нет .

Answer 3

Да, для сложности наихудшего случая. Но только если длина / шаг внутреннего цикла == длина / шаг внешнего цикла.