Article View: pl.comp.lang.python
Article #27197Re: Python a hashmapa
From: wodzik
Date: Sat, 09 Jan 2010 23:11
Date: Sat, 09 Jan 2010 23:11
19 lines
2004 bytes
2004 bytes
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, 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) Pozdrawiam wodzik
Technical Details
Message-ID:
<hib2ff$96o$1@zeus.man.szczecin.pl>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.gazeta.pl!newsfeed.pionier.net.pl!news.man.szczecin.pl!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>Show Full Headers
Complete Article Headers
Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.gazeta.pl!newsfeed.pionier.net.pl!news.man.szczecin.pl!not-for-mail From: wodzik <wodzik@noreply.com> Newsgroups: pl.comp.lang.python Subject: Re: Python a hashmapa Date: Sun, 10 Jan 2010 00:11:51 +0100 Organization: ACI - http://www.aci.com.pl Lines: 20 Message-ID: <hib2ff$96o$1@zeus.man.szczecin.pl> 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> NNTP-Posting-Host: 212.14.0.154 Mime-Version: 1.0 X-Trace: zeus.man.szczecin.pl 1263078703 9432 212.14.0.154 (9 Jan 2010 23:11:43 GMT) X-Complaints-To: usenet@news.man.szczecin.pl NNTP-Posting-Date: Sat, 9 Jan 2010 23:11:43 +0000 (UTC) User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.1.5) Gecko/20091204 Thunderbird/3.0 In-Reply-To: <hiavmd$i2o$1@solani.org> X-Antivirus: avast! (VPS 100109-0, 2010-01-09), Outbound message X-Antivirus-Status: Clean Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit