Асимптотическое сравнение функций

Мне даны две функции: F1(n)=2n+20 и F2(n)=n+1. Я должен показать, какой из них лучше.

Наш лектор решал аналогичную задачу. Учитывая F1(n)=n2 и F2(n)=2n+20, он сделал:

F2(n)/F1(n)=(2/n)+(20/n2)

и он сказал, что всегда будет меньше 22, следовательно, 2n+20 лучше.

Я сомневаюсь, как решить эти типы сравнения между функциями. Я рассмотрел все вопросы, ранее заданные здесь, и не совсем понял это.

Также, если задано (an2+bn+c)=O(n2), помогите в выборе констант c1, c2, n0 такие, что

c1g(n) ≤ f(n) ≤ c2g(n).


algorithm math asymptotic-complexity
person user9440643    schedule 04.03.2018    source источник
comment
Это не кажется точным... n^2 лучше, чем 2n+20?   -  person Kevin    schedule 04.03.2018
comment
Извините за ошибку Между n^2 и 2n+20 Последняя функция работает лучше   -  person user9440643    schedule 04.03.2018
comment
Это зависит от вашего определения хорошего. Очевидно, что 2n+20 всегда больше, чем n+1 для положительного n.   -  person Nico Schertler    schedule 04.03.2018
comment
Да @nico, но можете ли вы доказать это математическими средствами? буду премного благодарен   -  person user9440643    schedule 04.03.2018
comment
Ну и разница (2n + 20) - (n + 1) = n + 19. И эта разница явно положительна для всех n > -19. Следовательно, 2n + 20 больше, чем n + 1 для всех n > -19.   -  person Nico Schertler    schedule 04.03.2018

Ответы (1)


arrow_upward
0
arrow_downward

Как указано в одном из комментариев, сначала необходимо определить лучшую сложность.

Вполне вероятно, что ваш лектор имеет в виду сложность C(n) лучше, чем K(n), тогда и только тогда, когда C(n) << K(n) (или с использованием обозначений Ландау C(n) = o(K(n))) равно n -> +Inf.

Если вы хотите сравнить две сложности F1(n) и F2(n), один из способов — проверить, сходится ли частное F2(n)/F1(n), и если да, то к какому значению. С F2(n) ~ n и F1(n) ~ n^2 F2(n)/F1(n) сходится к 0 и, следовательно, F1(n) доминирует над F2(n) к бесконечности. Вы бы сказали, что F1(n) лучше, учитывая принятое ранее языковое соглашение.

Обратите внимание, что "это (F2(n)/F1(n)) всегда будет меньше 22, и говорят, что 2n+20 лучше" не является правильным подходом к асимптотическому анализу в случае отношений доминирования (o(.) или эквивалентно <<) (сомневаюсь, что ваш лектор сказал это для F1(n) и F2(n), определенных выше).

В вашем последнем вопросе - не могли бы вы определить f(n) и g(n)?

person Alexandre Dupriez    schedule 04.03.2018