O (3^n) экспоненциальная временная сложность

Question

public void run(int n) 
    { 
     System.out.println(power(3, n)); 
    } 

public int power(int c, int n) 
{ 
    int result = 1; 
    for (int i = 0; i < c; i++) { 
     result *= n; 
    } 
    return result; 
} 

Этот код дает мне O (c^k) - экспоненциальную временную сложность?

Answer 1

Вычисление 3, поднятое до степени n, не имеет сложности O (3^n). Ваша сложность алгоритма - это просто O (c), поскольку он выполняет итерацию только c раз. Чтобы написать алгоритм O (3^n), одним из способов может быть запуск цикла for 3^n раз. Пример таких для петли:

for(long i = 0; i < Math.power(3, n); i++) 

Answer 2

делает этот код дает мне O (с^к) - экспоненциальная сложность времени?

No. power(c, N) выполняет c умножения/итерации цикла, поэтому О (С). И это означает, что (начиная с c является константой в run(n)), test(n) на самом деле O(1).

Другая вещь, чтобы отметить, что power(c, n) является вычисление п ^гр НЕ с ^п.

Answer 3

Чтобы быть честным, если вы чувствуете, как показывая ребят учить, конечно, что их постановка проблемы, вероятно, является не то, что они хотели, я бы просто сделать это таким образом:

for(int i = 0; i < c; i++) { /*your code here*/} 

Это в O (c), а так как O (c) является строгим подмножеством O (c ^k) для k> 1, оно также находится в O (c ^k). Вероятно, это не то, что люди обучают вашему курсу, вероятно, вы хотите написать цикл, который работает в Θ (c ^k).

---

На другой ноте:

с ^к и 3 ^п не то же самое. Предполагая, что длина вашего ввода равна n, c ^k - это постоянное время, в то время как 3 ⁿ - экспоненциальное время. Предполагая, что длина вашего ввода c, c ^k является полиномиальным, а 3 ⁿ является постоянным. Предполагая, что длина вашего ввода равна k, c ^k является экспоненциальным, а 3 ⁿ является постоянным.