以下方法的複雜程度如何？

Question

我仍在學習使用Big O Notation進行復雜度測量，想知道是否正確地說，下面的方法的複雜性是O（n * log4n），其中「4」是下標。

public static void f(int n) 
{ 
    for (int i=n; i>0; i--) 
    { 
     int j = n; 
     while (j>0) 
      j = j/4; 
    } 
} 

Answer 1

是的，你是正確的，該功能的複雜性是O(n*log_4(n))

Log_4(n) = ln(n)/ln(4)和ln(4)是恆定的，所以如果你的函數具有複雜O(n*log_4(n))這也是事實，它具有的複雜性O(n*ln(n))

Answer 2

您的意思是

public static void f(int n) 
{ 
    for (int i=n; i>0; i--) 
    { 
     int j = i; // Not j = n. 
     while (j>0) 
      j = j/4; 
    } 
} 

？

在這種情況下，你也是對的。它是O（nlogn）。使用4作爲下標也是正確的，但它只會使編寫起來更加麻煩。

即使使用j=n一行，也是O（nlogn）。

事實上，要更準確地說，你可以說它是Theta（n logn）。

Answer 3

是的，你是對的，複雜就是n * LOG4（N）