Какова временная сложность секунды для l oop в следующем вложенном l oop?

Question

Я пытаюсь проанализировать время выполнения (Big-Oh) некоторых фрагментов кода и следующий, с которым у меня возникают проблемы:

for(i=0; i<n; i++){
    for(j=0; j<i*i; ++j) { 
         //random stuff here costs O(1)
    }
}

Первый l oop - это O (n ) но во втором l oop, я * я сбрасываю меня. Какова временная сложность для второго l oop? Пожалуйста, не указывайте общую сложность времени, так как это могло бы дать ответ целиком. Только советы, советы или ресурсы будут полезны! Спасибо!

Answer 1

Давайте проанализируем, что i*i на каждом шаге. Сначала его 0, затем 1, затем 4, затем 9 ...

Итак, в общем мы смотрим на

Это Это хорошая новость, есть закрытый от этого суммирования, вы можете доказать правильность путем индукции в качестве упражнения. Здесь я считаю само собой разумеющимся, что

И если вы знакомы с big-O, легко увидеть, как мы пришли к выводу, что O является O ( п ^ 3). Вот еще чтение некоторых общих сумм, которые часто встречаются в CS, я рекомендую взглянуть https://brilliant.org/wiki/sum-of-n-n2-or-n3/