Сравнение сложности алгоритмов

Question

В настоящее время я изучаю время выполнения Big O Notation и время амортизации.

У меня следующий вопрос:

Два алгоритма, основанные на принципе Divide & Conquer, доступны для решения проблемы сложности n. Алгоритм 1 делит задачу на 18 небольших задач и требует O (n ^ 2) операций, чтобы объединить подрешения вместе. Алгоритм 2 разделяет задачу на 64 небольших задачи и требует O (n) операций для объединения подрешений вместе.

Какой алгоритм лучше и быстрее (для больших n)?

Я предполагаю, что второй алгоритм лучше, потому что он требует меньше времени (O (n) быстрее, чем O (n ^ 2)). Я прав в своем предположении?

Количество мелких проблем играет роль в скорости алгоритма или всегда требует постоянного времени?

Answer 1

В этом случае он, вероятно, не предназначен для ловушки, но хорошо быть осторожным, и могут произойти некоторые нелогичные вещи.Ловушка, если она случается, в основном такова: насколько меньше подзадачи, по сравнению с тем, сколько их генерируется?

Например, для алгоритма 1 здесь верно, что если подзадачапроблемы составляют 1/5 от размера текущей проблемы или меньше (и, возможно, они имели в виду, что они будут иметь 1/18 размера?), тогда общая сложность времени в O (n²).Но если размер проблемы уменьшается только в 4 раза, мы уже достигли O (n ^2.085 ), и если домен был разрезан только пополам (но все еще в 18 раз), товсе идет вплоть до O (n ^4.17 ).

Аналогично алгоритму 2, убедитесь, что если программа разбивается на 64 подзадачи, каждая из которых составляет 1/64 от размера,общая сложность по времени будет в O (n log n).Но если подзадачи даже немного больше, скажем, 1/63 от размера, сразу мы поднимаемся на целый шаг в иерархии до O (n ^1.004 ) - крошечная константа в показателе степени все еще, но больше не логиново.Сделайте задачи на 1/8 размера, а сложность станет квадратичной, и если мы перейдем к простому уменьшению размера задачи на два шага на каждом шаге, то все будет вплоть до O (n ⁶ )!С другой стороны, если проблемы уменьшаются только на немного немного, скажем, на 1/65 размера, сразу же сложность перестает быть логарифмированной, но на этот раз в другом направлении, становясь O (n).

Таким образом, это может пойти в любую сторону, в зависимости от того, насколько быстро сокращаются подзадачи, что явно не указано в вашей постановке задачи.Надеемся, что ясно, что простого сравнения «дополнительной обработки на шаг» недостаточно, в общем, в любом случае.Большая обработка на шаге - это недостаток, который не может быть преодолен, но наличие лишь небольшой обработки на шаге - это преимущество, которое может быть легко потеряно, если «коэффициент усадки» мал по сравнению с «фактором разветвления».

Answer 2

Основная теорема используется для асимптотического анализа алгоритмов «разделяй и властвуй» и даст вам возможность получить прямой ответ, а не угадать.

T(n) = aT(n/b) + f(n)   

где T - основная проблема, n - набор входных данных, a - количество подзадач, на которые вы делитесь, b - коэффициент, на который уменьшается ваш входной набор для каждой подзадачи, и f(n) - функция разделения и объединения подзадач.Отсюда мы находим c:

f(n) is O(n^c)

Например, в вашем примере алгоритм 1, c = 2, а в алгоритме 2 c = 1. Значение a равно 18 и 64 для алгоритма 1 и 2 соответственно,В следующей части в вашей проблеме отсутствует соответствующая информация, поскольку b не указан. Другими словами, чтобы получить четкий ответ, вам нужно знать коэффициент, по которому каждая подзадача делит исходные данные.

if c < logb(a) then T(n) is O(n^logb(a))
if c = logb(a) then T(n) is O(n^c log(n))
if c > logb(a) then T(n) is O(f(n))