Рассмотрим следующую функцию:

Question

int unknown(int n){ 

int i, j, k=0; 
for (i=n/2; i<=n; i++) 
    for (j=2; j<=n; j=j*2) 
        k = k + n/2; 
 return (k); 

} 

Возвращаемое значение функции - Θ (n ^ 2logn).

Мое сомнение: временная сложность функции составляет Θ (nlogn), что я не понимаю, как это может быть Θ (nlogn), потому что внешний l oop будет выполняться ровно n / 2 раз, а внутренний l oop выполнит logn раз.

Чем сложность времени отличается от возвращаемого значения этой функции, может ли кто-нибудь объяснить мне простым языком, чтобы я мог это визуализировать.

Answer 1

Время, затрачиваемое функцией (рассчитанное по количеству l oop итераций), составляет приблизительно (n / 2) * (lg n).

Для каждой итерации k увеличивается на n / 2.

Таким образом, временная сложность равна O (n lg n), а возвращаемое значение функции в n / 2 раза больше, или O (n ^ 2 lg n).

Answer 2

Функция имеет 2 цикла i и j. i увеличивается с n / 2 до n, поэтому я выполню nn / 2 + 1 раз. Для j l oop начинается с 2 и заканчивается на n, и увеличивается экспоненциально: ie 2, затем 4,8 ... до logn раз. Таким образом, для этого количество итераций равно logn + 1 раз. Для каждой итерации в j есть приращение k на n / 2, поэтому общая сумма ie его возвращаемое значение., Которое O (n ^ 2logn). а общая временная сложность - O (nlogn), так как оператор должен выполнять это много раз.