Найти временную сложность функции «Foo»

Question

Я изо всех сил, чтобы найти временную сложность этой функции:

void foo(int n) { 
    int i, m = 1; 
    for (i = 0; i < n; i++) { 
     m *= n; // (m = n^n) ?? 
    } 
    while (m > 1) { 
     m /= 3; 
    } 
} 

Ну, первое для итерации явно O(n^n), объяснение к нему потому что m started with value 1, и умножает себя n раз.

Теперь мы начинаем цикл while с m = n^n, и каждый раз мы делим его на 3. это означает, (думаю), log(n^n).

Предполагая, что я понял это до сих пор, я не уверен, нужно ли мне суммировать или умножать, но моя логика говорит, что мне нужно их суммировать, потому что они являются «странными» друг для друга.

Так что мое предположение: O(n^n) + O(log(n^n)) = O(n^n) Потому что, если n довольно велико, мы можем просто воздержаться от O(log(n^n)).

Ну, я действительно сделал много предположений здесь, и я надеюсь, что это имеет смысл. Мне бы хотелось услышать ваше мнение о временной сложности этой функции.

Answer 1

Теоретически, сложность времени O(n log n), потому что:

for (i=0; i<n; i++) 
    m *= n; 

это будет осуществляться в п раз и в конце концов m=n^n

Тогда этот

while (m>1) 
    m /= 3; 

будут выполнены log3(n^n) раз, который является n * log3(n):

P.S. Но это только если вы подсчитаете количество операций. В реальной жизни требуется больше времени для вычисления n^n, потому что цифры становятся слишком большими. Кроме того, ваша функция будет переполнение, когда вы будете умножая такие большие числа и, скорее всего, вы будете ограничены максимальным числом int (в этом случае сложность будет O(n))

Answer 2

С foo(int n) и 32-разрядные int, n не может превышают величину 10, иначе m *= n переполнения.

Учитывая такой небольшой диапазон, что n работает, O() кажется спорным. Даже с 64-битным неподписанным m, n <= 15.

Поэтому я полагаю O (п Л.Г. (п)) является технически правильным, но с учетом ограничений int, подозреваемый код занимает больше времени, чтобы сделать один printf() чем перебирать foo(10). IOWs это практически O (1).

unsigned long long foo(int n) { 
    unsigned long long cnt = 0; 
    int i; 
    unsigned long long m = 1; 
    for (i = 0; i < n; i++) { 
    if (m >= ULLONG_MAX/n) exit(1); 
    m *= n; // (m = n^n) ?? 
    cnt++; 
    } 
    while (m > 1) { 
    m /= 3; 
    cnt++; 
    } 
    return cnt; 
} 

И придумали

1 1 
2 3 
3 6 
4 9 
5 12 
6 16 
7 19 
8 23 
9 27 
10 31 
11 35 
12 39 
13 43 
14 47 
15 52