Złożoność czasu Java O (n^2/3)

Question

Moje pochodzenie matematyczne nie jest tak dobre, to jest moja próba napisania kodu JAVA z proporcjami czasu runtime dla różnych danych wejściowych.

1. Z n^2/3. Od n^2/3 = kostki główny pierwiastek n * n, tym samym może napisać

   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. z 4^N. Czy mogę korzystać z metody Fibonnaci?

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

mogę wiedzieć, czy mój kod powyżej jest poprawna? dzięki wielkie!

Answer 1

Czy właśnie piszesz jakiś kod, który wymaga czasu złożoności tego big-o-bound?

Niż od 1, tak, zajęłoby O(n^(2/3)).

Ale dla # 2, twój kod zajmie O(2^n) i theta(1.6...^n), a 1.6 .. jest słynny złoty stosunek liczby.

referencyjny: Computational complexity of Fibonacci Sequence

Answer 2

Pierwszym z nich jest poprawna, i bardzo dobrze przemyślane.

---

Drugi nie jest. Algorytm obliczania kłamstw ma znacznie większą złożoność czasową niż O (n^4) (EDIT: , o co pytano, kiedy pisałem tę odpowiedź - w międzyczasie zaktualizowano pytanie:). To nawet nie jest wielomian. Rozumowanie jest następujący (#fib notacją (X): w szereg razy fib nazywa obliczyć fib (x))

• fib (1): #fib (1) = 1 (to zwraca się bezpośrednio z wynik)
• fib (2): #fib (2) = 3 (jeden dla fib (2), który wywołuje go dla fib (0) i fib (1))
• fib (3): #fib (3) = 5 (jeden dla fib (3), który wywołuje go dla fib (2) i fib (1), co daje 3 + 1 więcej połączeń)
• 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)

Tak, masz:

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

Od tego, to byłoby uzasadnione przypuszczenie, że obliczenia fib (I) trwa „o "(faktycznie, tylko trochę mniej niż) 2 razy więcej czasu na obliczenie kłamstwa (i-1). W związku z tym można "zgadywać", że O (#fib (i)) = O (2^i). To jest poprawna odpowiedź, którą możesz łatwo dowieść dzięki indukcji.

Aby ukończyć temat sekwencji Fibonacciego, istnieje znacznie szybsze algorytmy do obliczenia liczby n-tej. Na przykład, algorytm z czasem liniowym (tj. O (n)) ma na celu zapamiętanie tej funkcji, którą napisałeś (tzn. Sprawić, by skonsultował się z mapą, aby sprawdzić, czy zna wynik dla n, jest tak zwrócony natychmiast, w przeciwnym razie, obliczyć zapisz i zwróć). Istnieje również algorytm stałokresowy (tzn. O (1)).

---

Wreszcie przykład O (N^4) algorytm jest cokolwiek z wewnętrznej pętli 4, każda pętla działa "o" n razy.

Na przykład, obliczenia objętości N kostki o boku n (w nieoptymalnej sposób):

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

Nie jest to odpowiedź, ale tutaj jest szkic „oszukiwać” rozwiązania do problemu dostarczenia przykładu programu, który zajmuje O(F(N)) czas;

1. utworzyć funkcję obiektu Java, aby ocenić F(N) dla danego N:

2. przekazać go jako parametr do następującej metody:

---

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) 
     } 
    } 

---

Ale nie używaj tego, jeśli istnieje ryzyko utraty kredytu za bycie "inteligentnym ** s" :-)