сложности времени, когда J + = SQRT (я)

Question

Мне нужно найти временную сложность (в терминах теты) эта функция:

int x = 0; 
for (int i=1; i < n ; i++) { 
    for (double j=i; j <= n ; j+=sqrt(i)) { 
    ++x; 
    } 
} 

Я знаю, что внешний цикл делает N-1 итерации и внутренние loop выполняет (ni)/sqrt (i) итерации, поэтому мне нужно рассчитать сигма i = 1-n-1 of (ni)/sqrt (i). Любая идея, как это сделать?

EDIT: Предположим, что sqrt() работает в O (1).

Answer 1

Я не знаю, что такое сигма и тэта, но sqrt - операция с постоянным временем, поэтому в основном это не имеет значения в большой записи O, т.е. j + = sqrt (i); совпадает с j + = i; совпадает с j + = 1 ;. Также (n-k) ~ = n для k много меньше n. Это означает, что при n больших n-i это просто n. Итак (n-i) * sqrt() = n * 1 = n. И вы делаете это n раз для внешнего цикла, так что n^2.

Дополнение Как к вашей сложной серии, я уверен, что это точно, но это не то, что мы заботимся о том, что мы заботимся о порядке работы. Поэтому нам нужно показать, что ваша серия O (n^2) или K * n^2. Итак, у вас есть i + 2 * i + ... (n-1) * i + n * i. Где i является постоянным, поэтому мы можем его разложить и завернуть в K и оставить 1 + ... + n. В этом утверждении доминирует n, т. Е. Когда n получает большие n ~ = (n-1) и (n-1) ~ = (n-2), откуда следует, что (n-2) ~ = n. Теперь это не выполняется по мере приближения к нулю, но n настолько велико, что мы можем отказаться от первого миллиона слов. поэтому мы остаемся с некоторой функцией, которая выглядит как C * (n-k) * n + c. где C, k и c - постоянные. Поскольку мы не заботимся о константах, мы просто заботимся о росте по мере роста n, мы можем отбросить все эти константы и просто сохранить n^2. В качестве альтернативы вы можете показать, что ваша серия ограничена n^k * n, где k переходит к одному, когда n приближается к бесконечности, но хороший логический аргумент обычно лучше. ~ Бен