В анализе алгоритма, что на самом деле означает «для некоторой константы с»?(Например, быстрая сортировка)

Question

Рассмотрим следующее дерево рекурсии для быстрой сортировки, которое постоянно делит подзадачи на соотношение 3: 1 (источник: Академия Хана ).

Я понимаю, что подпрограмма секционирования в быстрой сортировке перебирает каждую подзадачу и, таким образом, равна O(n).Однако меня смущает, почему «Общее время разбиения для всех подзадач» составляет cn, а не просто n.Что представляет собой константа в этом случае?Когда / почему это будет что-нибудь, кроме 1?Является ли c чем-то, что вы можете решить, или, скорее, «концептуальной» переменной?

Если я правильно понимаю, подпрограмма раздела посещает каждый элемент в данной подзадаче ровно один раз.И поскольку размер суммы всех подзадач на каждом уровне равен n, разве это не означает, что точно n работа выполняется на каждом уровне (по крайней мере, до границы log n / log4)?

Спасибо

Answer 1

Что представляет собой константа в этом случае?Когда / почему это будет что-то, кроме 1?

Давайте перевернем вопрос и посмотрим, когда это будет ровно 1. На этот вопрос просто ответить.

Это будет 1, когдаесть только один шаг.Поэтому, когда мы делаем что-то, кроме одного шага, значение будет различным.

В случае разделения некоторые из других вещей, которые мы делаем, являются вычислением новой границыподразделов (если мы разбиваем массив) или создаем новые списки (если мы разбиваем список).

Является ли c тем, что вы можете решить, или, более того, «концептуальным»"variable?

Да, вы можете успешно попытаться найти значение c для каждого уровня и определить его значение, но в случае Big-O это не будет значимым усилием, поскольку Big-Oигнорирует константы.

... поскольку суммарный размер всех подзадач на каждом уровне равен n, разве это не означает, что n работа выполняется на каждом уровне (по крайней мере, доlog n / log4 границы)?

Нет.Как видно из двух под-ответов выше, работа не 1 * n, но (some book-keeping, etc. steps) * n, также равна c * n.

Answer 2

Когда / почему это будет что-то кроме 1?

В нижней части строки log4 (n) общее время разделения указано как «cn». Поскольку самая левая ветвь дерева стека на этом уровне имеет только один элемент, это означает, что это операции «c» даже в случае одного элемента, и что конец каждой ветви дерева стека с одним элементом будет принимать «с» операции. Сложность по времени игнорирует константы, поэтому, если время разделения равно «c», то сложность по времени равна O (1). Если время разбиения равно «cn», то сложность по времени равна O (n).

Единственное, что меняется, когда дерево стека идет глубже, чем log4 (n), это общее количество обрабатываемых элементов меньше n, поэтому общее время разбиения для этого уровня составляет <"cn", а в правом нижнем углу в стеке дерева только один элемент - это процесс со временем разбиения "c". </p>

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

Answer 3

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

РЕДАКТИРОВАТЬ: я имел в виду, что c отличается для каждой реализации.