Что такое большое о нотации следующих

Question

Я не могу понять, наименьшие верхние барьеры для этих двух

я думал о LOG3 (п) для первого и O (п!) Для второго, но я не уверен в этом, потому что я не очень понял тему

public int ex1 (int n) { 
    int r = 0 ; 
    for (int i = 1 ; i < n ; i++) { 
     r += n ; 
     n = n/3 ; 
    } 
    return r ; 
} 

public static int ex5 (int n) { 
    int r = 1 ; 
    for (int i = 0 ; i < n ; i ++) { 
     r += ex5 (n - 1) ; 
    } 
    return r ; 
} 

Answer 1

Выходные значения EX5 соответствуют sequence A000522 at oeis.org, что увеличивает как (п) = sum_ {к = 0..n} п!/К! (или n! в первом приближении). Из-за ужасного способа кодирования этой функции это совпадает со сложностью времени функции.

Гораздо лучше алгоритм будет выглядеть следующим образом:

public static int ex5 (int n) { 
    return (n) ? 1 + n * ex5(n-1) : 1; 
} 

, который, очевидно, O (N^2) O (п) ^{(К сожалению, уже поздно, и мне нужно спать!)}.

EDIT: Как все остальные говорят, сложность EX1 является O (log_3 (п)), или просто O (журнал (п)), так как log_3 (п) = журнала (п)/журнал (3), а log (3) - постоянная в любой базе.

Answer 2

Первый будет выполняться до i < log_3(N) и это можно сказать, что O(log_3(N))

Второй, кажется, рекурсия рекурсий. Кажется, что функция возвращает i! раз за каждый i < N.

F(3) = {F(2) + F(1)} + {F(1)} 
F(4) = {F(3) + F(2) + F(1)} + {F(2) + F(1)} + {F(1}} 

Answer 3

В каждом случае вам просто нужно учитывать, сколько итераций происходит в пределах for -loop.

1. ex1 = O(log(n))for -loop итерации log3(n) раз

   r = n/30 + n/31 + n/32 + n/33 + ... + n/3log3(n)

2. ex5 = O(n!) для-петли итерация n раз для f(n) и каждая итерация называет f(n-1) так что общие итерации |f(n)| = n*|f(n-1)| , где |f(n)| = # of iterations in f(n). Используя это рекурсивно дает:

   |f(n)| = n|f(n-1)| 
        = n(n-1)|f(n-2)| 
        = n(n-1)(n-2)|f(n-3)| 
        ... 
        = n(n-1)(n-2)...(3)(2)|f(0)| 
        = n! 
   

Answer 4

Первое упражнение:

Второе упражнение (очень дорогой алгоритм, следует избегать):

Обратите внимание, что выполнение общего дела ион является одним факторизованным на c, а подошва n! указывает количество базовых футляров (ex5(0) == 1). Суммирование обоих дало бы точное количество рекурсивных вызовов.