Я чувствую время работы следующей функцииПродолжительность функции
int sum = 0;
for (int i = 1; i < 1000; i ++) {
for (int j = 0; j < i; j++){
sum++;
}
}
является O(N^2) N = число раз внешний цикл выполняется и
int sum = 0;
for (int i = 1; i < 1000; i*=2){
for (int j = 0; j < i; j++){
sum++;
}
}
является O(2^N) N = число раз, когда внешний цикл работает Насколько я понимаю, правильно?
Первый O (N^2), потому что он делает, добавляет все числа от 1 до N, и, как вы знаете, что решается с помощью следующей формулы:
(N + 1) N/2 which has O(N^2) time complexity.
вторая добавляет все силы 2 от 1 до 1000, которая решается с помощью этой функции:
2^(n + 1) - 2
НО, в этой формуле n максимальная степень 2 в серии и 2^п является фактически число преобладает N, поэтому нам нужно поставить его в терминах N:
2^(n+1) - 2 <= N * 2 - 2 which has O(N) time complexity.
для N = 9, 2^(n +1) - 2 = 1022 и 2N -2 равно 16. Существует большая разница между ними. Я чувствую 2^(n + 1) -2> = 2N-2. поэтому временная сложность должна быть O (2^N) или, как утверждает andrey, она должна быть O (N log N). – Siva
В качестве примера попробуйте различные значения 'N'. Если «N» равно 4, тогда время равно «1 + 2 + 4 = 7», которое равно «4 * 2- 1», если «N» равно 8, тогда время равно «1 + 2 + 4 + 8 = 15 'который является' 8 * 2- 1', если 'N' равно 16, тогда время равно' 1 + 2 + 3 + 4 + 8 + 16 = 31', которое равно '16 * 2- 1'. – imreal
Упрощает первую проблему, позволяя N=10, наружный проход i=1..N петли, а внутренний цикл выполнения j=1..i.
Каждая строка представляет собой одну итерацию внешнего цикла, число точек, указывающее, сколько раз внутренний цикл запускается для этой итерации.
i | j
1 | .
2 | . .
3 | . . .
4 | . . . .
5 | . . . . .
6 | . . . . . .
7 | . . . . . . .
8 | . . . . . . . .
9 | . . . . . . . . .
10 | . . . . . . . . . .
Суммируя все j «S дает нам общее количество раз, когда внутренний блок запускается на выполнение:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 .
формула для последовательной суммы из 1..N является:
N*(N+1)/2 = 0.5N^2 + 0.5N = O(N^2)
Второй является 'O (N войти N)'. Где «N = 1000» ........ –