Логика, лежащая в основе этих определений, на самом деле довольно проста, в основном она говорит о том, что независимо от того, какие константы умножают результат, с некоторой точки, где n достаточно велика, одна из функций начнет становиться больше / меньше иэто так и остается.
Чтобы увидеть реальную разницу, я объясню th small-o (который говорит, что одна функция имеет меньшую сложность, чем другие), он говорит, что для всех k больше нуля вы можете найтинекоторое значение n, называемое n_0, для которого все n больше n_0 следует этому шаблону: f(n) <= k*g(n).
Таким образом, у вас есть две функции, и вы помещаете туда n в качестве параметра,Тогда независимо от того, что вы указали как k, вы всегда найдете значение n, для которого f(n) <= k*g(n) и все значения, которые больше, чем найденное вами, также будут вписываться в это уравнение.
Учтитенапример:
f(n) = n * 100
g(n) = n^2
Так что, если вы попытаетесь поместить, например, n=5, он не скажет вам, что имеет большую сложность, потому что 5*100=500 и 5^2=25.Если вы поставите число достаточно большое, то есть n=100, то f(n)=100*100=10000 и g(n)=100^2=100*100=10000.Таким образом, мы получаем то же значение.Если вы попытаетесь поставить что-то большее, g (n) будет становиться все больше и больше.
Оно также должно следовать уравнению f(n) <= k*g(n).Например, если я поставлю то есть k=0.1, то
100*n <= 0.1*n^2 *10
1000n <= n^2 /n
1000 < n
Итак, с помощью этих функций вы можете увидеть, что для k=0.1 у вас есть n_0 = 1000 для выполнения уравнений, но этого достаточно.Все n > 1000 будут больше, а функция g(n) всегда будет больше, поэтому сложнее.(хорошо, настоящее доказательство не так просто, но вы можете увидеть шаблон).Дело в том, что независимо от того, что будет k, даже если оно равно k=0.000000001, всегда будет точка разрыва n_0, и с этого момента все g(n) будут больше f(n)
Мы также можем попробовать некоторые отрицательные уравнения, чтобы увидеть разницу между O(n) и O(n^2).
Давайте возьмем:
f(n) = n
g(n) = 10*n
Итак, в стандартной алгебре g(n) > f(n),право?Но в теории сложности нам нужно знать, растет ли он больше, и если да, то растет ли он больше, чем просто умножается на константу.
Так что, если мы рассмотрим это k=0.01, то вы можете видеть, что независимо от того, какбольшим будет n, вы никогда не найдете n_0, который удовлетворяет f(n) <= k*g(n), поэтому f(n) != o(g(n))
С точки зрения теории сложности вы можете принять обозначения как меньшие / большие, так что
f(n) = o(g(n)) -> f(n) < g(n)
f(n) = O(g(n)) -> f(n) <= g(n)
f(n) = Big-Theta(g(n)) -> f(n) === g(n)
//... etc, remember these euqations are not algebraic, just for complexity