Можете ли вы помочь мне рассчитать сложность времени этого алгоритма?

Question

public static void complexityexample(int n) { 
    int count = 0; 
    int k = 1; 
    for (int i = 0; i < n; i++) { 
     for (int j = 0; j < k; j++) { 
      count++; 
     } 
     k *= 2; 
     for (int t = 0; t < n; t++) { 
      count++; 
     } 
     System.out.println(count); 
    } 
} 

Может ли кто-нибудь написать мне ответ?

, например, я знаю, что Колличесто операций в течение цикла равна 2N + 2,

и количество операций в подсчете ++; is N

но какие-либо другие детали.

Answer 1

Сложность времени O(2n). Бутылка шея:

for(int j = 0; j < k; j++){ 
    count++; 
} 

С k экспоненциально возрастает с каждой итерацией i.

В i 'итерация, k = 2i-1. Это означает, что итерация всех значений от j до k составляет O(k) = O(2i).

Теперь Суммируя все это для всех итераций:

 
20 + 21 + 22 + ... + 2n-1 = 2n - 1 

Где последнее равенство происходит от sum of geometric series

Обратите внимание, что следующий внутренний цикл:

for (int t = 0; t < n; t++) { 

не влияющий на время сложность (в терминах асимптотической нотации), поскольку она добавляет O(n) время для каждой итерации i, и это получает q под влиянием экспоненциального поведения первого внутреннего цикла.

Если вы хотите, чтобы подсчитать стоимость count в конце концов, это суммирование первого внутреннего контура, который, как сказал это (2n)-1, а второй внутренний цикл, который sum{n | for each i} = n2.

Answer 2

(2^п) + (N * N)

как их основной цикл является

for (int i = 0; i < n; i++) { 

2^п от:

for (int j = 0; j < k; j++) { 
     count++; 
    } 

и п * п из :

for (int t = 0; t < n; t++) { 
     count++; 
    } 

Answer 3

1-я строка) 1 операция.

2-й ряд) 2 операции.

3-я строка) 1 + n + 1 + n = 2N + 2.

4) 2N + 2

5) N

7) N

9) 2N + 2

10) N

13) 1

Это правильно.

И после всех математических вычислений конечный результат: 14N^2 + 22N + 11 - операции.

Answer 4

Точная методика с использованием Sigma обозначений будет:

Эмпирически проверено:

При п = 10, количество общих итераций 1123.

При п = 25, количество итераций в целом равно 33555056.

Когда n = 50, потребовалось навсегда выполнение (мне пришлось изменить переменную s от int до long).

Действительно, этот не полиномиальный алгоритм дорог.