Метод грунтовки Big-O Сложность

Question

Когда вы рассматриваете сложность метода, который вызывает рекурсивный метод (метод учебника для начинающих), учитываете ли вы сложность рекурсивного метода или просто учитываете вызов метода.

Например, У меня есть небольшая программа, которая вычисляет последовательность Фибоначчи:

// Complexity: ???
public int fib() {
    int n = 9;
    return fib(n);
}


// Complexity: O(2^n)
private int fib(int n) {
    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

Сложность рекурсивного метода fib(int n) равна O(2^n), но я не уверен, какой будет сложность fib().

Я предполагаю, что это сложность 1, потому что все, что он делает, это определяет и int и возвращает число.

Answer 1

Я предполагаю, что это сложность 1, потому что все, что он делает - это определяет и возвращает int и возвращает число. ... " это не правда. Значение f(9) также вычисляется . (Он может быть вычислен во время «компиляции», но, тем не менее, он вычисляется.) Поскольку предпосылка вашего аргумента не является строго правильной ... никакого вывода сделать нельзя.

Игнорирование этого спора, ваше объяснение интуитивно верно, но оно не соответствует строгой математической перспективе.

Лучшее объяснение - выбрать некоторую математическую переменную (скажем, Q). Затем мы можем сказать, что временная сложность fib() равна O(1) относительно этой переменной .

(Обратите внимание, что n не является переменной в этом контексте, более чем pi или e являются переменными.)

Или вы можете сказать, что анализ сложности fib() не имеет смысла, если вы не определите интересующую входную переменную.

Эти два взгляда на это имеют больше смысла с математической точки зрения (ИМО). Принятые математические определения O предполагают, что существует переменная. Сложность O характеризует поведение функции относительно этой переменной.