Complessità del tempo Java O (n^2/3)

Question

Il mio background matematico non è così buono, questo è il mio tentativo di scrivere il codice JAVA con proporzione di runtime su input diversi.

1. Con n^2/3. Poiché n^2/3 = radice cubica n * radice cubica n, quindi posso scrivere

   public void test(int n){ 
       for (int i = 0; i*i*i < n; i++) { 
        for (int j = 0; j*j*j < n; j++) { 
         count ++; 
        } 
       } 
   } 
   

2. Con 4^n. Posso usare il metodo Fibonnaci?

   public int fibonnaci(int n) { 
       if (n <= 1) { 
        return 1; 
       } else { 
        return fibonnaci(n - 2) + fibonnaci(n - 1); 
       } 
   } 
   

si può sapere se il mio codice di cui sopra è corretto? grazie mille!

Answer 1

Stai semplicemente scrivendo un codice che richiede una complessità temporale di tale limite?

Rispetto al numero 1, si, ci vorrebbe O(n^(2/3)).

Ma per il numero 2, il tuo codice prenderà O(2^n) e theta(1.6...^n) e 1.6 .. è il famoso numero di golden-ratio.

di riferimento: Computational complexity of Fibonacci Sequence

Answer 2

La prima è corretta, e davvero ben pensato.

---

Il secondo non è. Quell'algoritmo per calcolare i fib ha una complessità temporale molto più alta di O (n^4) (EDIT: che era quello che veniva chiesto quando ho scritto questa risposta - la domanda è stata aggiornata nel frattempo). Non è nemmeno polinomiale. Il ragionamento è il seguente (#fib notazione (x): numero di volte fib è chiamato a calcolare fib (x)):

• fib (1): #fib (1) = 1 (restituisce direttamente la risultato)
• fib (2): #fib (2) = 3 (uno per fib (2), che lo chiama per fib (0) e fib (1))
• fib (3): #fib (3) = 5 (uno per fib (3), che lo chiama per fib (2) e fib (1), dando 3 + 1 chiamate in più)
• fib (4): #fib (4) = 9
• fib (5): #fib (5) = 15
• fib (6): #fib (6) = 25
• ...
• fib (i): #fib (i) = 1 + #fib (i-1) + #fib (i-2)

Quindi, si ha:

• #fib (i) ~ = #fib (i-1) + #fib (i-2)

Da questo, sarebbe un'ipotesi ragionevole che il calcolo fib (i) prende "su "(in realtà, solo un po 'meno di) 2 volte il tempo per calcolare fib (i-1). Quindi, potresti "indovinare" che O (#fib (i)) = O (2^i). Questa è la risposta corretta, che puoi dimostrare facilmente per induzione.

Giusto per finire sulla sequenza di Fibonacci, ci sono algoritmi molto più veloci per calcolare il numero n-esimo. Per esempio, un algoritmo con tempo lineare (cioè, O (n)) è quello di memoizzare quella funzione che hai scritto (cioè, fai in modo di consultare una mappa per verificare se conosce il risultato per n, è quindi di restituirla immediatamente, altrimenti calcola lo memorizza e restituiscilo). C'è anche un closed formula to calculate the n-th fib, quindi un algoritmo a tempo costante (cioè, O (1)).

---

Infine, un esempio di O (n^4) algoritmo è nulla con 4 cicli interni, ogni ciclo in esecuzione "di" n volte.

Ad esempio, calcolare il volume di n cubi di lato n (in modo non ottimale):

int volume = 0; 
for (int cube = 0; cube < n; cube++) 
    for (int x = 0; x < n; x++) 
    for (int y = 0; y < n; y++) 
     for (int z = 0; z < n; z++) 
     volume++; 
return volume; 

Answer 3

Questo non è proprio una risposta, ma qui è uno schizzo di una soluzione "ingannare" al problema di fornire un esempio di un programma che richiede tempo O(F(N));

1. Creare una funzione oggetto Java per valutare F(N) per un dato N:

2. passarla come parametro al metodo seguente:

---

public void computeOrderFN(int n, FunctionInt2Int fn) { 
     int count = fn.evaluate(n); 
     for (int i = 1; i < count; i++) { 
      // Do something O(1) that the compiler can't optimize away) 
     } 
    } 

---

Ma non usare questo se c'è il rischio di perdere credito per essere "una smart ** s" :-)