Article View: pl.comp.lang.python
Article #27198Re: Python a hashmapa
From: Stachu 'Dozzie' K.
Date: Sun, 10 Jan 2010 12:19
Date: Sun, 10 Jan 2010 12:19
33 lines
2740 bytes
2740 bytes
On 2010-01-09, wodzik <wodzik@noreply.com> wrote: > On 2010-01-09 23:24, Stachu 'Dozzie' K. wrote: > >> To ze szkoły powinieneś wiedzieć że to nie do końca daje złożoność O(1). > > Powiedz to moim wykładowcom, albo chociaż by Thomasowi Cormenowi. > Cytując z książki "Wprowadzenie do algorytmów": > -"Przy rozsądnych założeniach można wykazać, że oczekiwany czas > wyszukiwania elementu z tablicy z haszowaniem wynosi O(1)." > czy: > -"średni czas działania podstawowych operacji słownikowych na tablicy z > haszowaniem wynosi O(1)." > > Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2 > takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje, ...a gdy tych elementów o jednakowych kluczach robi się bardzo dużo, to szlag trafia gwarancje czasowe, czyli dokładnie to co mówię... > jednak w porównaniu z złożonością liniową O(n) dla większej ilości > elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność > jest O(1), a nie np. O(1.3) O(1.3) jest w ogóle bez sensu dla kogokolwiek, kto wie co to jest złożoność obliczeniowa, bo to jest dokładnie O(1). A przypadek jest dość istotny, bo wpływa i na pesymistyczną, i na zamortyzowaną złożoność obliczeniową, tylko zwyczajowo się zakłada że nie występuje. -- Secunia non olet. Stanislaw Klekot
Technical Details
Message-ID:
<hicgku$3k3$1@solani.org>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.gazeta.pl!newsfeed.pionier.net.pl!news-2.dfn.de!news.dfn.de!feeder.erje.net!weretis.net!feeder1.news.weretis.net!news.solani.org!not-for-mailReferences:
<hi9a48$c1b$1@zeus.man.szczecin.pl> <20100109102348.d563af8e.natural-born-killer@dontmailme.com> <hi9nmc$iqv$1@zeus.man.szczecin.pl> <hi9rbf$1ke$2@solani.org> <hiapsg$4mg$1@zeus.man.szczecin.pl> <hiavmd$i2o$1@solani.org> <hib2ff$96o$1@zeus.man.szczecin.pl>Show Full Headers
Complete Article Headers
Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.gazeta.pl!newsfeed.pionier.net.pl!news-2.dfn.de!news.dfn.de!feeder.erje.net!weretis.net!feeder1.news.weretis.net!news.solani.org!not-for-mail From: "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> Newsgroups: pl.comp.lang.python Subject: Re: Python a hashmapa Date: Sun, 10 Jan 2010 12:19:42 +0000 (UTC) Organization: solani.org Lines: 33 Message-ID: <hicgku$3k3$1@solani.org> References: <hi9a48$c1b$1@zeus.man.szczecin.pl> <20100109102348.d563af8e.natural-born-killer@dontmailme.com> <hi9nmc$iqv$1@zeus.man.szczecin.pl> <hi9rbf$1ke$2@solani.org> <hiapsg$4mg$1@zeus.man.szczecin.pl> <hiavmd$i2o$1@solani.org> <hib2ff$96o$1@zeus.man.szczecin.pl> Mime-Version: 1.0 X-Trace: solani.org 1263125982 3715 eJwNyckBwCAIBMCWWDmUcgiy/Zdg5juugeht4WFOp0x2mXFP4sS6HzQP9C52QTBiWqCIsv8TexiVEOE= (10 Jan 2010 12:19:42 GMT) X-Complaints-To: abuse@news.solani.org NNTP-Posting-Date: Sun, 10 Jan 2010 12:19:42 +0000 (UTC) X-User-ID: eJwNx8kBwCAIBMCWYDmWlKMo/Zdg5jdhqdn0jPSYmNGboJxCw+/fD217y1Yjy3JRQrvAM8YFexahEJk= Cancel-Lock: sha1:En4GsenG7nF0HsbCeVk04cOII3E= User-Agent: slrn/0.9.8.1 (Linux) X-NNTP-Posting-Host: eJwVx8EVADEEBcCWQvgoh6D/Evbt3EYvCM8ECtHVpQqTrg0R935U+Bs8jjOmPGmH83JuGqf3BxxtETg= Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit