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

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

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

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

Спасибо


sorting algorithm quicksort asymptotic-complexity
person A is for Ambition    schedule 17.05.2018    source источник
comment
Обработка разделяемого элемента требует затрат. Вы должны получить элемент, запустить сравнение, а затем поместить значение в нужное ведро. Время, затрачиваемое на c на каждый разбиваемый элемент.   -  person btilly    schedule 18.05.2018
comment
Когда вы говорите ровно n работать, что это значит? Что такое 1 работа? Я знаю, что мы говорим о времени, но это минута? Второй? микросекунда? Разве это не зависит от того, сколько вы заплатили за свой компьютер?   -  person Matt Timmermans    schedule 18.05.2018

Ответы (3)


arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

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

person displayName    schedule 18.05.2018

arrow_upward
2
arrow_downward

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

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

person OrdoFlammae    schedule 18.05.2018
comment
c является константой. Это не отличается для каждой итерации. Возможно, вы имели в виду, что он отличается для использования с каждой реализацией. - person rici; 18.05.2018
comment
Это правда. И да, именно это я и имел в виду. Спасибо что подметил это. - person OrdoFlammae; 18.05.2018

arrow_upward
2
arrow_downward

Когда/почему это может быть что угодно, кроме 1?

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

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

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

person rcgldr    schedule 18.05.2018