Какова сложность следующего метода?

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

да вы правы, сложность п * log4 (п)