Dlaczego nie da się stworzyć takiego algorytmu?

0

Witam, dzisiaj na uczelni jeden z profesorów zadał następujące pytanie: "Dlaczego nie da się stworzyć żadnego algorytmu z porównaniem działającego w czasie krótszym niż O(nlogn)?".
Głowię się już nad nim pół dnia i nie za bardzo wiem jak podejść do tematu. Czy ktoś byłby w stanie mi to wytłumaczyć?

8

Dla tych którzy nie rozumieją o co autor pyta: Dlaczego dolnym pesymistycznym ograniczeniem złożoności obliczeniowej dla algorytmu sortowania opartego o porównywanie elementów jest O(nlogn)

Dowód: https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

0
Adam Królikowski napisał(a):

Witam, dzisiaj na uczelni jeden z profesorów zadał następujące pytanie: "Dlaczego nie da się stworzyć żadnego algorytmu z porównaniem działającego w czasie krótszym niż O(nlogn)?".
Głowię się już nad nim pół dnia i nie za bardzo wiem jak podejść do tematu. Czy ktoś byłby w stanie mi to wytłumaczyć?

Jest algorytm linowy do sortowania, znaczy: O(n), więc to co sugerujesz to bzdura.

najgłupszy - naiwny schemat wygląda tak:
mając serię, czyli tablicę, elementów n-bitowych, wystarczy wprost przepisać tę tabelę,
używając elementów tejże tablicy w roli indeksów, czyli jakoś tak to wygląda - z grubsza:
a[e[i]] = i;
i = 1..n, więc to wymaga dokładnie n operacji, nie więcej.

4

@fol nie doczytałeś że chodzi o algorytmy oparte o porównywanie elementów. To co opisałeś czyli CountingSort, tak samo jak wszystkie podobne rozwiązania typu RadixSort nie opierają się o porównywanie elementów!
Jednocześnie te algorytmy wymagają O(k) pamięci żeby złożoność wynosiła O(n*k). Żeby mieć faktycznie O(n) to zakres danych k musiałby być bardzo mocno ograniczony. Co wiecej nadaje sie to jedynie do sortowania liczb naturalnych, bo każde inne dane trzeba by mapować do intów. A takie mapowanie, czyli hashowanie. Niestety nigdy nie jest idealne i albo ryzykujemy O(n) na czas dostępu do elementów, przy użyciu hashmap, co oznaczałoby że dostaniemy pesymistycznie złożoność O(n^2) zamiast spodziewanego O(n) ;]

0
Shalom napisał(a):

@fol nie doczytałeś że chodzi o algorytmy oparte o porównywanie elementów. To co opisałeś czyli CountingSort, tak samo jak wszystkie podobne rozwiązania typu RadixSort nie opierają się o porównywanie elementów!

Tu też jest porównywanie - inaczej nie byłoby sortowania.

a[i] < a[i+1];

Jednocześnie te algorytmy wymagają O(k) pamięci żeby złożoność wynosiła O(n*k). Żeby mieć faktycznie O(n) to zakres danych k musiałby być bardzo mocno ograniczony. Co wiecej nadaje sie to jedynie do sortowania liczb naturalnych, bo każde inne dane trzeba by mapować do intów. A takie mapowanie, czyli hashowanie. Niestety nigdy nie jest idealne i albo ryzykujemy O(n) na czas dostępu do elementów, przy użyciu hashmap, co oznaczałoby że dostaniemy pesymistycznie złożoność O(n^2) zamiast spodziewanego O(n) ;]

Ogólnie jest jakaś taka reguła: złożoność obliczeń można łatwo zmniejszyć, ale wtedy potrzeba więcej pamięci.

1

@fol bzdura, CountingSort nie wymaga żadnych porównań między elementami a mimo to sortuje bez problemu ;) Popatrz: https://pl.wikipedia.org/wiki/Sortowanie_przez_zliczanie#Przyk.C5.82adowa_implementacja_w_j.C4.99zyku_C.2B.2B

0
Shalom napisał(a):

@fol bzdura, CountingSort nie wymaga żadnych porównań między elementami a mimo to sortuje bez problemu ;) Popatrz: https://pl.wikipedia.org/wiki/Sortowanie_przez_zliczanie#Przyk.C5.82adowa_implementacja_w_j.C4.99zyku_C.2B.2B

A. Porównanie to taka operacja, która bierze dwa argumenty i produkuje wynik typu: równe, mniejsze, większe.
B. Sortowanie taka operacja, która bierze n argumentów i produkuje wynik typu: a[1] <= a[2] <= a[3] <= ...

3

@fol no i co w związku z tym? Przecież cała zabawa polega na tym że da się posortować dane BEZ konieczności porównywania ze sobą elementów i na tym opierają się metody sortujące w czasie poniżej O(nlogn). Czy ty umiesz w ogóle czytać? Może ten kod był dla ciebie za trudny? To wyjaśnie słowno-muzycznie:
Jeśli policzysz sobie że w zbiorze wejściowym nie masz zera, masz 2 jedynki, żadnych dwójek, 3 trójki i 1 czwórkę to nie potrzeba niczego porównywać ze sobą bo wystarczy że wygenerujesz sobie zbiór wyjściowy jako [1,1,3,3,3,4].
A do takiego policzenia nie trzeba znów niczego porównywać ze sobą bo robisz tablica[liczba]++ i w indeksie liczba w tablicy będziesz miał informacje o tym ile elementów o danej wartości wystąpiło. Znów niczego tu nie porównujemy.

0
Shalom napisał(a):

@fol no i co w związku z tym? Przecież cała zabawa polega na tym że da się posortować dane BEZ konieczności porównywania ze sobą elementów i na tym opierają się metody sortujące w czasie poniżej O(nlogn).

A kto powiedział, że w sortowaniu należy wprost używać operatora a < b?

Jeśli policzysz sobie że w zbiorze wejściowym nie masz zera, masz 2 jedynki, żadnych dwójek, 3 trójki i 1 czwórkę to nie potrzeba niczego porównywać ze sobą bo wystarczy że wygenerujesz sobie zbiór wyjściowy jako [1,1,3,3,3,4].
A do takiego policzenia nie trzeba znów niczego porównywać ze sobą bo robisz tablica[liczba]++ i w indeksie liczba w tablicy będziesz miał informacje o tym ile elementów o danej wartości wystąpiło. Znów niczego tu nie porównujemy.

Dla posortowanej serii danych masz relację typu: ai < aj, dla każdego i < j;
No i co to jest - gdzie masz operację porównywania elementów?

Jedynie liczby można porównywać i szeregować.
zielony < ogień < tłusty < łysy < mucha - co to jest?

3

@fol, spotkałeś się kiedyś z uporządkowaną alfabetycznie listą nazwisk? Masz bardzo ubogą wiedze matematyczną skoro twierdzisz, że tylko liczby można porównywać i szeregować.

1

Jedynie liczby można porównywać i szeregować.

Skończ ty może wreszcie gimnazjum a usłyszysz o takich rzeczach jak: relacja, porządek czy element największy/najmniejszy. Mówi się o tym na Algebrze i wyobraź sobie że nie dość że da się "porównywać" dowolne obiekty z dowolnych przestrzeni to w ogóle sama "relacja" też moze być bardzo luźno zdefiniowana. Relacja < czy > dla liczb to jest tylko bardzo szczególny przypadek, który pokazuje się dzieciom w szkole podstawowej.
Zerknij może na przykład na http://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt2/skrypt/node9.html ;]

Bo ja sobie mogę zdefniować np. relacje krótszy na zbiorze słów nad alfabetem ascii i ta moja relacja może być tak zdefiniowana, że x krótsze od y zachodzi kiedy liczba liter w słowie x jest mniejsza niż liczba liter w słowie y. I zaręczam ci ze można posortować zbiór słów nad alfabetem ascii zgodnie z tą relacją.
Mogę też zdefiniować relacje bardziej brzuchaty znów na zbiorze słów nad alfabetem ascii i relacja jest tak zdefiniowana że x bardziej brzuchate od y zachodzi kiedy liczba brzuszków w literkach w słowie x jest większa niż liczba brzuszków w literkach w słowie y. I znów wyobraź sobie że możemy posortować zbiór słów nad alfabetem ascii zgodnie z tą relacją!

Brakuje ci wyobraźni...

0
bogdans napisał(a):

@fol, spotkałeś się kiedyś z uporządkowaną alfabetycznie listą nazwisk? Masz bardzo ubogą wiedze matematyczną skoro twierdzisz, że tylko liczby można porównywać i szeregować.

Z tego masz jedynie taki wniosek: nazwiska, jak i wszelkie inne serie liter, czy dowolnych symboli, są równoważne z liczbami.

Co jest zresztą oczywiste!

np.: 'Lolek' = 5 bajtów, tym samym to jest liczba 5x8 = 40 bitowa.
'Kozłowski' = liczba 9B, itd.

Można to oczywiście redukować, np. 26 literek to mniej niż 32, czyli 5 bitów na każdą.
Zatem dowolne słowo n-literowe to 5 x n bitowa liczba.

Niemniej liczba słów - nazw w dowolnym języku, nie przekracza chyba nawet 1 miliona,
co daje 20 bitów zaledwie = 5 symboli średnio na string!
Dobranoc.

0
Shalom napisał(a):

Jedynie liczby można porównywać i szeregować.

Skończ ty może wreszcie gimnazjum a usłyszysz o takich rzeczach jak: relacja, porządek czy element największy/najmniejszy. Mówi się o tym na Algebrze i wyobraź sobie że nie dość że da się "porównywać" dowolne obiekty z dowolnych przestrzeni to w ogóle sama "relacja" też moze być bardzo luźno zdefiniowana. Relacja < czy > dla liczb to jest tylko bardzo szczególny przypadek, który pokazuje się dzieciom w szkole podstawowej.

Relacja posządkowa typu: mniejszy, jest właśnie relacją liczb (naturalnych itp.).

Liczby zespolone - co to jest?
1 + i > 2 - i - prawda to?

pewnie że nie!

Możesz jedynie liczby porównywać, zatem w przypadku zespolonych nie istnieje rel. mniejszości,
podobnie jak w przypadku dowolnych wektorów!

|a| > |b| - to jest ok zawsze, nawet dla wektorów i kolorów, bowiem porównujesz tu liczby - normy!

Brakuje ci wyobraźni...

Doucz się podstaw matematyki.

3

@fol nie no ty nadal nie rozumiesz że relacja będzie taka jak to sobie zdefiniujesz. I to są właśnie podstawy Algebry których ci brakuje. Oczywiście że mogę sobie zdefiniować dowolną relacje porządku w zbiorze liczb zespolonych bo i czemu nie? To że nie ma żadnej "ogólnie przyjętej" relacji nie ma żadnego znaczenia. Mogę sobie zdefiniować relacje < na zbiorze liczb zespolonych taką że x<y jeśli re(x) < re(y), bo kto mi zabroni?

Możesz jedynie liczby porównywać,

Ciekawe, a jednak wyżej pokazałem dwa przykłady relacji porządku która szereguje słowa a nie liczby, więc jak to sie stało? Magia?

Zresztą nadal nie bardzo rozumiem o co ci tutaj chodzi bo piszesz nie dość że od rzeczy to jeszcze nie na temat. Udowodniłem ci wyżej że da się uporządkować zbiór obiektów bez konieczności porównywania ze sobą par takich obiektów i można to zrobić w czasie liniowym względem liczby sortowanych elementów. Jednocześnie wyżej wisi dowód na to, że jeśli chcesz sortować poprzez porównywanie elementów ze sobą to dolnym ograniczeniem złożoności obliczeniowej jest O(nlogn). Co tu jest jeszcze niejasne?

0
Shalom napisał(a):

@fol nie no ty nadal nie rozumiesz że relacja będzie taka jak to sobie zdefiniujesz. I to są właśnie podstawy Algebry których ci brakuje. Oczywiście że mogę sobie zdefiniować dowolną relacje porządku w zbiorze liczb zespolonych bo i czemu nie? To że nie ma żadnej "ogólnie przyjętej" relacji nie ma żadnego znaczenia. Mogę sobie zdefiniować relacje < na zbiorze liczb zespolonych taką że x<y jeśli re(x) < re(y), bo kto mi zabroni?

Nie improwizuj bo się tylko ośmieszasz.
Nie istnieje relacja prządku w zespolonych, i tak samo dla (x,y,z) i dowolnych innych wektorów...

Mniejszość to jest relacja liczb - skalarów, i koniec!

Zresztą nadal nie bardzo rozumiem o co ci tutaj chodzi bo piszesz nie dość że od rzeczy to jeszcze nie na temat. Udowodniłem ci wyżej że da się uporządkować zbiór obiektów bez konieczności porównywania ze sobą par takich obiektów i można to zrobić w czasie liniowym względem liczby sortowanych elementów. Jednocześnie wyżej wisi dowód na to, że jeśli chcesz sortować poprzez porównywanie elementów ze sobą to dolnym ograniczeniem złożoności obliczeniowej jest O(nlogn). Co tu jest jeszcze niejasne?

Co jest niejasne?
Bredzicie jak dzieci po ciemku.

3

"Nie istnieje relacja prządku w zespolonych, i tak samo dla (x,y,z) i dowolnych innych wektorów..."
Nieprawda, relacja (x,y)<=(a,b) <=> x<=a oraz y<=b jest relacją porządku, nie jest relacją liniowego porządku. Rozróżnienie tych pojęć chyba Cię przerasta. Polecam lekturę tego artykułu https://en.wikipedia.org/wiki/Partially_ordered_set, szczególnie uważnie przeczytaj sekcję Examples.

"Z tego masz jedynie taki wniosek: nazwiska, jak i wszelkie inne serie liter, czy dowolnych symboli, są równoważne z liczbami."
Próbujesz to zdanie uzasadnić poetyckim bajdurzeniem. Jeśli chcesz to zdanie uzasadnić, to podaj przykład funkcji f: zbiór Stringów -> zbiór liczb takiej,że String s poprzedza alfabetycznie String t <==> f(s)<=f(t).

2

W ZFC, na każdym zbiorze (w szczególności więc na ℂ) można zadać dobry porządek, więc w szczególności liniowy… A o takie relacje nad niektórymi przestrzeniami wektorowymi, na przykład ℝ¹, jest bardzo łatwo.

Wróżę perełkę.

0

Z tematu o algorytmach sortowania doszliście do relacjach porządku w liczbach zespolonych, nieźle :D.

0

Reasumując te wasze improwizacje:
nie istnieje algorytm sortowania typu in-situ o złożoności mniejszej od n^2!

I niech ktoś teraz spróbuje to podważyć!

Z góry obalam tezę, że niby qsort ma złożoność nlogn, a tym samym obala moją tezę.

Qsort nie jest wcale algorytmem typu in-situ,
ponieważ ta metoda wymaga dodatkowej pamięci w ilości rzędu log(n)!
co jest sprzeczne z założenie in-situ!

Podobnie jest z sortowaniem stogowym, które również ma złożoność nlog(n).

0
Shalom napisał(a):

@fol ty jesteś po prostu upośledzony czy próbujesz nieudolnie trollować?

nie istnieje algorytm sortowania typu in-situ o złożoności mniejszej od n^2!
I niech ktoś teraz spróbuje to podważyć!

Obawiam się że już spróbowali i z całkiem dobrym skutkiem:
https://arxiv.org/pdf/cs/0305005.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.8523&rep=rep1&type=pdf
https://www.researchgate.net/profile/Klaus_Reinhardt/publication/226473909_Sorting_in-place_with_a_worst_case_complexity_of_n_log_n-13nOlog_n_comparisons_and_e_n_log_nO1_transports/links/0deec5193d91cc4998000000.pdf

Twoje przykłady nie są sortowaniem typu 'w miejscu', podobnie jak qsort,
Próbuj dalej...

0

Ty w ogóle do nich zerknąłeś? Nie, nie odpowiadaj, wiem ze nie. Za dużo mądrych słów i wzorów :D No ale zerkamy na sam abstrakt pierwszego z brzegu a tam:

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports.

Faktycznie, ewidentnie:

nie są sortowaniem typu 'w miejscu'

A autorzy tych publikacji to jakieś kmioty, nie to co @fol :D

0
Shalom napisał(a):

Ty w ogóle do nich zerknąłeś? Nie, nie odpowiadaj, wiem ze nie. Za dużo mądrych słów i wzorów :D No ale zerkamy na sam abstrakt pierwszego z brzegu a tam:

Tak.

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports.

Podobnie mówi się że qsort ma złożoność nlogn, co jest prawdą, niemniej metoda nie typu in-situ, ponieważ wymaga ekstra ramu w ilości lon(n),
co jest sprzeczne z założeniem: in-situ.

A autorzy tych publikacji to jakieś kmioty, nie to co @fol :D

A co mnie obchodzi co dzieci sobie improwizują na ćwiczeniach w szkole?

Pamiętam ze szkoły, że był nawet taki facet, który twardo się uparł, że światło to cząstki - strumienie cząstek,
zwane obecnie fotonami (z analogi do fononów dźwiękowych).
No i cóż z tego wynikło? Nic, oczywiście.

Morał z tego jest prosty:
żadne takie naiwne, szkolne improwizacje nie mają żadnego znaczenia w praktyce.

0
fol napisał(a):
Shalom napisał(a):

Ty w ogóle do nich zerknąłeś? Nie, nie odpowiadaj, wiem ze nie. Za dużo mądrych słów i wzorów :D No ale zerkamy na sam abstrakt pierwszego z brzegu a tam:

Tak.

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports.

Podobnie mówi się że qsort ma złożoność nlogn, co jest prawdą, niemniej metoda nie typu in-situ, ponieważ wymaga ekstra ramu w ilości lon(n),
co jest sprzeczne z założeniem: in-situ.

A autorzy tych publikacji to jakieś kmioty, nie to co @fol :D

A co mnie obchodzi co dzieci sobie improwizują na ćwiczeniach w szkole?

Pamiętam ze szkoły, że był nawet taki facet, który twardo się uparł, że światło to cząstki - strumienie cząstek,
zwane obecnie fotonami (z analogi do fononów dźwiękowych).
No i cóż z tego wynikło? Nic, oczywiście.

Morał z tego jest prosty:
żadne takie naiwne, szkolne improwizacje nie mają żadnego znaczenia w praktyce.

Totalny mindfuck!
Od sposobów sortowania do korpuskularno-falowej natury światła... gigant! :D

edit:
chodzi oczywiście o Newtona, ale później to zostało uzupełnione m.in Younga, de Broglie'a, Plancka, Shroedingera i wielu innych. Fizyka ma wielu ojców :)

0

A cóż za różnica - fotony czy sortowanie?

Łamiąc tylko jeden jedyny raz najmniejsze z praw logiki, można potem już jechać swobodnie... pierdzielić brednie w nieskończoność!

Co też pokazuję od razu!
po wymyśleniu fotonu momentalnie powstała cała ta współczesna zajebista.. fizyka kwantowa:
EPR paradoksy, twierdzenie Bella, itd.

I cóż to jest?
To jest to samo, czyli szkolne urojenia głupiutkich dzieci, i nic więcej!

Notabene, ten pan Bell był studentem gdy te swoje głupoty publikował..
Zatem miał prawo te swoje pierdoły opowiadać... bo nie dziwota że nie rozumiał podstaw algebry - jak każde dziecko.

|a + b| <= |a| + |b|
dla niego nawet ta trywialna nierówność była niepojmowalna!
a co dopiero takie coś:
|a - b| <= 1-ab :)

0

@fol:

*I can live with doubt and uncertainty. I think it’s much more interesting to live not knowing than to have answers which might be wrong. *
-- Richard P. Feynman

https://phys.org/news/2013-09-scientists-never-before-seen.html

0

@fol przykro mi ale zdradzasz największe tajemnice wszechświata i nie możemy na to pozwolić. Wysyłam w twoim kierunku oddział reptalian oraz dwa samoloty z chemtrails... :D

0

Wystarczyły dwa słówka i już wymiękliście.

No i gdzie teraz wasz dowód, że można sortować szybciej niż o(n^2) z ograniczeniem 'in situ'?
A w dupie... utonął, i razem z fotonami, oczywiście.

Dobranoc frajerzy.

0

Przecież przedstawiłem ci 3 różne publikacje z algorytmami i dowodami. No ale skoro jesteś za głupi zeby je zrozumieć, to nie wiem czego oczekujesz :) Mam wrażenie ze liczysz na przeniesienie do Perełek, ale zmartwie cię. Tam trafiają rzeczy śmieszne, a twoja ignoracja jest raczej smutna...

0
Shalom napisał(a):

Przecież przedstawiłem ci 3 różne publikacje z algorytmami i dowodami. No ale skoro jesteś za głupi zeby je zrozumieć, to nie wiem czego oczekujesz :) Mam wrażenie ze liczysz na przeniesienie do Perełek, ale zmartwie cię. Tam trafiają rzeczy śmieszne, a twoja ignoracja jest raczej smutna...

Przestań marudzić mi tu... zapisz ten swój algorytm to zobaczymy co i jak.

Nie mam zamiaru analizować dziesiątek stron studenckich wypocin.
Programowanie to dziedzina stricte ścisła, a nie jakieś tam populistyczne gadanie, które ci amatorzy prezentują (bo tyle tylko potrafią!).

1 użytkowników online, w tym zalogowanych: 0, gości: 1