Обозначение Big Theta и временная сложность цикла

Мне сказали сделать функцию на основе цикла, которая возвращает n-е число Фибоначчи. Я уже сделал функцию и включу ее ниже. В моем задании говорится: «Утверждать, что время работы функции равно Θ(n), т. е. функция линейна по n». В книгах, которые я читал, и видео, которые я смотрел, Big-Theta всегда записывалась как Θ(g(n)) и выражалась в виде некоторого неравенства. Инструктор отказывается отвечать на какие-либо вопросы по этому поводу, пока мы не сдадим его.

Вот два моих вопроса:

1) Буду ли я прав, если скажу, что мой g(n) равен 5n+7 и что Θ(n) линейно, потому что g(n) линейно?

2) Нужно ли мне беспокоиться о верхних и нижних границах, даже если эта функция имеет линейное время выполнения?

int fib(int n)
{
    int fib = 1;                                    //1
    int num1 = 0;                                   //1
    int num2 = 1;                                   //1

    for(int i = 0; i < n; i++)                      // 1 + (n+1) + 1
    {
            fib = num1 + num2;                      //2n
            num1 = num2;                            //1n
            num2= fib;                              //1n
    }
    return fib;                                     //1
}                                                   //----------------
                                                    //5n+7 <- runtime as a function of n

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


person Chris Douglas    schedule 17.07.2017    source источник
comment
Я был бы осторожен с назначением фактических значений времени для каждой операции, потому что, хотя добавление занимает всего половину цикла на большинстве современных процессоров, чтение/запись может занять до 80.   -  person meowgoesthedog    schedule 17.07.2017
comment
Не говоря уже о том, что компилятор делает с этим фрагментом и как он будет выглядеть в итоге. Вот почему O-нотации так полезны, потому что они абстрагируются от всех ссылок на время и деталей реализации. Вы можете создать собственный ЦП, который выполняет все операции за один цикл. Но все равно пришлось бы зацикливаться n раз.   -  person SkryptX    schedule 17.07.2017


Ответы (1)


1) Буду ли я прав, если скажу, что мой g(n) равен 5n+7 и что Θ(n) линейно, потому что g(n) линейно?

Да вроде. Я бы не советовал вам когда-либо называть определенное g(n), потому что вы понимаете, что язык программирования не является хорошим представлением математической функции. Вы можете запрограммировать свою функцию рекурсивным образом и провести совершенно другой анализ, или это даже будет невозможно так, как вы это сделали. Но что остается неизменным, так это то, что ваш алгоритм всегда выполняет O(n) и пропорционален Θ(g(n)) с g(n) = n.

Чтобы понять разницу между O(g(n)) и Θ(g(n)), посмотрите здесь: Что такое разница между Θ(n) и O(n)?

2) Нужно ли мне беспокоиться о верхних и нижних границах, даже если эта функция имеет линейное время выполнения?

Нет, не знаешь. Не в этом алгоритме. В алгоритме Фибоначчи нет лучшего или худшего случая, поэтому он всегда заканчивается Θ(n). Обратите внимание, что я использовал Big-Theta, а не O-обозначение, потому что время выполнения равно n, а не максимум n.

person SkryptX    schedule 17.07.2017
comment
Хорошо! Это имеет смысл! O(n) похоже на худший сценарий. Так что, если бы я не хотел звучать как болван, я мог бы сказать, что 5n+7 состоит из O(n), а также из Θ(n), потому что O(n) и Θ(n) пропорциональны друг другу? - person Chris Douglas; 17.07.2017
comment
Я бы не стал сравнивать O(n) и Θ(n). В частности, Θ(n) не обязательно должно существовать, но если оно существует, O(n) равно Θ(n) (однонаправленному!!), потому что Θ(n) является более сильной границей, чем O(n). Я бы сказал, что алгоритм имеет одинаковую верхнюю и нижнюю границу пропорциональности n и, следовательно, подходит для Big-Theta Θ(n). Это все. - person SkryptX; 17.07.2017