Какой алгоритм является лучшей временной сложностью?

Question

Я читал о нотации Big-O. Я понял какую-то идею, но при сравнении двух алгоритмов я не понял, что какая-то вещь выглядит следующим , он говорит, что существует два алгоритма.

First f2(n) = 2n + 20 steps. 
second f3(n) = n + 1 steps. 
he write f2 = O(f3): 

    f2(n)/f3(n) 
    =((2n + 20)/(n + 1))<= 20; 
    he say Certainly f3 is better than f2?, of course f3 = O(f2), this time with c = 1. 

Я думаю, что f3 лучше, чем f2, потому что меньше факторов. мои вопросы

1) почему постоянный c = 1, как он это выбирает? 2) почему f3 = O (f2) и почему f2 = O (f3)?

Answer 1

Это обе линейные функции, поэтому оба являются O(n) и оба O друг друга. f3 в 20 раз быстрее, асимптотически, чем f2. Все это одновременно верно.

Answer 2

Ответ Patrick87 объясняет немного больше об асимптотическом характере нотации Big-O. Я покажу вам немного больше этого. Давайте рассмотрим f2 и f3 немного более тесно:

Во-первых, f2(n): Мы знаем, что f2(n) = O(2n + 20). 20 является константой, поэтому мы можем игнорировать ее. Итак, f2(n) = O(2n + 20) = O(2n). Опять же, 2 является константой, поэтому мы также можем ее игнорировать, поэтому: f2(n) = O(2n + 20) = O(2n) = O(n).

Что означает этот анализ является то, что n возрастает, функция, 2n + 20 растет так же быстро, как функция, которая является 2n, которая растет так же быстро, как функция, которая является n. Это имеет смысл, если вы думаете об этом: все эти функции являются параллельными линиями. Их темпы роста одинаковы.

В настоящее время f3(n): Мы знаем, что f3(n) = O(n + 1). 1 является константой, поэтому мы можем ее игнорировать. Итак, f3(n) = O(n).

И поэтому f3 и f2 оба являются O(n). Это не означает, что эти функции принимают то же самое время за заданное значение n или f2 так же быстро, как f3 в такт. Это просто означает, что сложность (т. Е. Время, затрачиваемое на выполнение работы) обеих функций увеличивается с той же скоростью , поскольку n увеличивается.