Какова лучшая сложность жадного алгоритма?

Question

Кажется, что лучшая сложность была бы линейной O (n).

Не имеет значения, на самом деле, я говорю о жадных алгоритмах в целом.

Иногда стоит быть жадным?

В конкретном случае, который меня интересует, будет вычисление изменений.

Скажем, вам нужно дать 35 центов в обмен. У вас есть монеты 1, 5, 10, 25. Жадный алгоритм, закодированный просто, решит эту проблему быстро и легко. Сначала набираем 25 центов, самое высокое значение - 35, а затем следующие 10 центов, чтобы завершить итог. Это было бы в лучшем случае. Конечно, есть плохие случаи и случаи, когда у этого жадного алгоритма были бы проблемы. Я говорю о лучшей сложности случая для определения этого типа проблемы.

Answer 1

Когда вы говорите о жадных алгоритмах, обычно вы говорите о правильности алгоритма, а не о сложности времени, особенно для таких проблем, как внесение изменений.

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

Answer 2

Любой алгоритм, который выводит n элементов, которые должны быть взяты индивидуально, имеет в лучшем случае O(n) сложность времени;жадные алгоритмы не являются исключением.Более естественная жадная версия, например, проблема с рюкзаком, превращает что-то с NP-завершением во что-то, что O(n^2) - вы пробуете все предметы, выбираете тот, который оставляет меньше всего свободного места;затем попробуйте все оставшиеся, выберите лучшее снова;и так далее.Каждый шаг O(n).Но сложность может быть любой - это зависит от того, насколько трудно быть жадным.(Например, алгоритм жадной кластеризации, такой как иерархическая агломерационная кластеризация, имеет отдельные шаги, которые O(n^2) для оценки (по крайней мере наивно), и требует O(n) этих шагов.)

Answer 3

GREEDY APPROACH

1. проблема с рюкзаком ... отсортировать данный элемент с помощью сортировки слиянием .. (nlogn)
2. найти максимальный срок, который займет O (n)
3. используя линейный поиск, выберите один за другим элемент .... O (n²)

nlogn + n + n² = n² в худшем случае ....

теперь можномы применяем бинарный поиск вместо линейного поиска .....?

Answer 4

Жадный или нет, по сути, не имеет ничего общего с вычислительной сложностью, за исключением того факта, что жадные алгоритмы, как правило, проще, чем другие алгоритмы, для решения той же проблемы, и, следовательно, они, как правило, имеют меньшую сложность.