Влияет ли изменение n на O алгоритма?
Влияет ли манипулирование n на O алгоритма?
рекурсивный код, например:
Public void Foo(int n)
{
n -= 1;
if (n <= 0) return;
n -= 1;
if (n <= 0) return;
Foo(n)
}
Влияет ли переназначение n на O(N)? Звучит интуитивно для меня...
Есть ли в этом алгоритме O(N) за счет отбрасывания константы? Технически, поскольку он уменьшает n на 2, он не будет иметь такого же математического эффекта, как этот:
public void Foo(int n) // O(Log n)
{
if (n <= 0) return;
Console.WriteLine(n);
Foo(n / 2);
}
Но разве деление n пополам не будет способствовать O(N), поскольку вы касаетесь только половина количества n? Чтобы было ясно, я изучаю нотацию O и ее тонкости. Я искал случаи, похожие на первый пример, но мне трудно найти такой конкретный ответ.
@Sebastian Это было целью моего собственного кода. Я просто не знал на 100%, как к этому относиться, с точки зрения Большого О. Не хотел распространять какую-то неточную чепуху, лол.
Ответы 1
Переназначение самого n на самом деле не имеет значения, когда речь идет о нотации O. В качестве примера рассмотрим простой цикл for:
for i in range(n):
do_something()
В этом алгоритме мы делаем что-то n раз. Это будет эквивалентно следующему алгоритму
while n > 0:
do_something()
n -= 1
И эквивалентна первой представленной вами рекурсивной функции. Итак, что действительно важно, так это то, сколько вычислений выполняется по сравнению с размером входных данных, который является исходным значением n. По этой причине все эти три алгоритма будут алгоритмами O(n), поскольку все три из них каждый раз уменьшают «входной размер» на единицу. Даже если бы они увеличили его на 2, это все равно был бы алгоритм O(n), поскольку константы не имеют значения при использовании нотации O. Таким образом, следующий алгоритм также является алгоритмом O(n).
while n > 0:
do something()
n -= 2
или
while n > 0:
do_something()
n -= 100000
Однако вторая рекурсивная функция, которую вы представили, представляет собой алгоритм O (log n) (хотя он не имеет базового случая и технически будет работать до переполнения стека), как вы написали в комментариях. Интуитивно понятно, что происходит, если каждый раз уменьшать размер ввода вдвое, это точно соответствует логарифму по основанию два от исходного входного числа. Рассмотрим следующее:
n = 32. Алгоритм каждый раз удваивается: 32 -> 16 -> 8 -> 4 -> 2 -> 1. Всего мы сделали 5 вычислений. Эквивалентно log2(32) = 5.
Итак, напомним, что имеет значение исходный размер входных данных и сколько вычислений выполняется по сравнению с этим размером входных данных. Какая бы константа ни влияла на вычисления, это не имеет значения.
Если я неправильно понял ваш вопрос или у вас есть дополнительные вопросы, не стесняйтесь комментировать этот ответ.
Как я и ожидал, это поможет победить дохлую лошадь: отбрасываемые константы не влияют на время выполнения, но могут оказать существенное влияние на производительность «в реальном мире». Это правильно?
Это определенно влияет как на производительность, так и на время выполнения, просто это не самый важный аспект при рассмотрении систем с чрезвычайно большими размерами входных данных. Это не значит, что вы не должны его учитывать. Если у вас есть база данных, содержащая, возможно, 100 000 записей, определенно имеет значение, используют ли ваши алгоритмы n вычислений или 2 n вычислений. Но гораздо важнее то, является ли алгоритм алгоритмом O(n) или O(n²), поскольку O(n) будет 100 000 вычислений, а O(n²) будет 10000000000 вычислений. Важность тем больше, чем больше n.
Отлично, спасибо. Это очень помогает. Я ценю подробный ответ! Использование нотации Big O гораздо шире, чем я изначально предполагал (я думаю). Крутая штука!
Забавное небольшое примечание о том, что нотация O — не единственное, что имеет значение, почитайте о Галактические алгоритмы. Первое, что пришло мне в голову, это то, что при выполнении матричных умножений текущий «самый быстрый» алгоритм - это галактические алгоритмы, которые не имели бы смысла в реальных практиках.
Большое спасибо за чтение!
Это хороший способ обойти нотацию
O(n)и упаковать больше операций :-)