Почему не сортировка бисера имеет теоретическую временную сложность O (n)?

Question

Как может Bead Sort имеют теоретическую временную сложность O (1)?

Wikipedia утверждает, что если каждый шарик перемещается одновременно, как и если бы вы использовали счеты для выполнения этого вида, тогда у вас была бы сложность времени O (1), но не было бы расстояния, которое бисер должен путешествовать в худшем и среднем случае по-прежнему масштаба с размером списка?

Если я недопонимаю статью, то что делает вызывают сложность времени (1)?

---

Также известен как силы тяжести Сортировка

Answer 1

O (1), является сложность в модели, где гранулы могут все падают сколь угодно большое расстояние в фиксированном количестве времени. Как говорится в статье, эта модель не точно отражает физическую реальность.

Answer 2

Каким образом может быть отсортировано по формуле (1)?

Когда все шарики разрешено падать в то же время паралельно как в Abacus, то гранулы устроили бы в порядке возрастания сверху вниз. Все это происходило бы в постоянное время, поэтому сложность была бы O (1).

Устройство будет представлять собой кучу бусин, расположенных в одной линии Абакуса; то же самое произойдет в каждой строке Abacus, и, следовательно, наибольшее количество бусин будет поселиться в последнем ряду, так как последняя строка будет состоять из бусинок в каждой строке Abacus.

Все это происходит из-за гравитации (непрактично допустимо допускать падение каждого шарика одновременно, но это всего лишь теоретическое предположение).

СЛУЧАЙ: -

*****       **** 
**********   ---->  ***** 
**************     ********** 
****       ************** 
// this happens in a short while because beads would settle to the lower surface 
// because of presence of Gravity. 

расстояние будет не важно здесь, так как это не должно рассматриваться для измерения сложности времени.

Википедия подчеркивает непрактичный случай:

времени сложность будет O (1): ^!Бусины все перемещаются одновременно в единицу времени, так как будет иметь дело с простым физическим примером выше. Это абстрактная сложность и не может быть реализована на практике.

_{! focus mine}