Я читаю «Введение в алгоритмы» и застрял в главе 3, где авторы говорят, что «что может быть удивительнее, когда при a> 0 любая линейная функция an + b равна в O (n^2)» Can кто-нибудь объясняет, как это доказать?Сложность времени a + b = O (n^2)?
Линейная функция an + b является O(n^2) по определению: при достаточно больших n, an + b меньше cn^2 с константой, например c = 1.
Отметьте, что O(n^2) является верхней границей, но не плотной. Не очень плотная связь не очень полезна, как только вы можете доказать более жесткую привязку (в данном случае верхняя граница O(n)).
Для интуиции идея «большой O» состоит в том, что, начиная с достаточно большого ввода, функция стоимости не растет быстрее, чем O (...). Это все, это просто верхняя граница.
Линейная функция не растет быстрее, чем квадратичная функция, кубические функции, экспоненциальная функция и т.д. Все они растут быстрее, следовательно, an + b является O(n^2), но и O(n^3), O(2^n), O(n!) и т.д.
Тем не менее, растет быстрее, чем логарифм - поэтому вы не можете сказать, что это O(log n).
Не могли бы вы предоставить более конкретное местоположение, чем «в главе 3», или, по крайней мере, объяснить обозначение «c b» в этом контексте? – Gassa