Сложность времени, когда j + = sqrt (i)

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

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

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

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

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. Итак, у вас есть я + 2 * я +... (n-1) * я + n * 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 приближается к бесконечности, но хороший логический аргумент обычно лучше. ~ Бен

licensed under cc by-sa 3.0 with attribution.