Навсякъде ги има

[линк]

Този мушмурок май си вярва -> О(1)

Зависи к'во сортира момчето -- масиви от байтове, примерно, си се сортират в линейно време без проблем ;)

Мхаха, тоя е от тия спецове дето викат, че алгоритмите били за пишкомерци под 35 години.

Хора без чувство за хумор винаги ще се намерят да почнат да го убеждават че бърка.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

тоя чува ли се




NE SUTOR ULTRA CREPIDAM

Тц-тц-тц... O(1)-то чак сега ме чукна по челото, първо го взех за O(n)...

Като се замисли човек, дори и така пича има право на претенции, чисто формално :) Ако има алгоритъм който да сортира за време F(n), и ако масива не може да е по-голям от N, това значи че сортировката е O( F(N) ) = O( const ) = O( 1 ) -- т.е., гарантирано в рамките на предварително зададено време (да не забравяме че дори динозаврите да се появят и изчезнат няколко пъти докато се сортира масива, тва няма голямо значение от гледна точка на теорията ;)

ако, се постави условието входния масив да е сортиран .

всеки алгоритъм е О(1)
тоест за да има смисъл да говорим въобще за разно Ота, то неограниченост на масива е задължително условие.
аз въобще не погледнах какво е писал оня, но дори О(н) би било велико постижение, макар че се съмнявам да е възможно.

В отговор на:

---

всеки алгоритъм е О(1)
тоест за да има смисъл да говорим въобще за разно Ота, то неограниченост на масива е задължително условие.
аз въобще не погледнах какво е писал оня, но дори О(н) би било велико постижение, макар че се съмнявам да е възможно.

---

Ами асимптотичния анализ се занимава и с такива задачи :)

Ако тариката е казал "имам O(1) алгоритъм за сортиране на масив от 100 000 елемента," това си е напълно валидно, теоретично издържано, и по всяка вероятност - вярно твърдение, ако ще да сортира с bubble sort ;)

Колкото до O-то на сортировките по принцип, (почти) всичко е възможно за определени множества входни данни. O( n log n ) е average case за сортиране на базата на сравнения, и обикновено това се има предвид под сортиране. Ако имаш практически ограничен value-space, обаче -- примерно, байтове, или дори short int -- може просто да направиш хистограма от която после да построиш сортирания масив, и всичко това да става в линейно време.

пише Implementation of Hoare's Quickshort algorithm. масив от байтове наистина може да се сортира с линейна сложност, но не и с този алгоритъм. a О(1) е даже по-малко от линейна.

unsigned

Ако всички байтове са само нули няма ли скоростта да е наистина О(1)?

Bеer? Mоre?
Плацебото

ми то си зависи от алгоритъма. ако имаш специален алгоритъм за сортиране на масив от нули, който не прави нищо, значи сложността е O(1). а ако не дай си боже решиш да си обходиш нулите, за да видиш дали са добре и как я карат, ефективността ти рязко пада на O(n).

unsigned

липсва ми образование - та да попитам :)

Bеer? Mоre?
Плацебото

Защо да не си вярва?!
Ако n = 1 си е абсолютно прав.


1 000 024... 1 000 025... 1 000 026...

не бях дочел условието

Айде, айде
Объркал се е човека. Смешно е да правите проблеми заради печатни грешки.
QuickSort e O(n*n) в най-лошия случай и че неможе да има по-добър от O(n*ln(n)) в най-лошия случай алгоритъм базиран на сравнения на елементи. Това даже и великите програмъри, дето я разбират бизнес-логиката го знаят.

Unix is user friendly, it's just very picky about who his friends are.