WebHU - Programozási kérdések és válaszok

Python bináris keresés (az iterációk maximális száma)

Bináris kereséssel gugliztam pythonban, és ezt találtam: http://openbookproject.net/thinkcs/python/english3e/list_algorithms.html

Azt mondta, hogy az általános kapcsolat a max. az iterációk számát (ugyanaz, mint a Probe?) és az N-t (a lista mérete) N = 2^k -1 adja meg, ahol k az iterációk maximális száma .

Értelmem szerint azonban az általános összefüggés nem lehet N = 2^k
Mint minden keresés után, a listát 2-vel osztjuk, amíg el nem jutunk 1-hez.

Ezért az iterációk maximális száma log2 (N+1) helyett log2 N

Kerestem a Google-on, és találtam egy webhelyet, amely alátámasztja a válaszomat, de sok magyarázat nélkül. (link itt: http://codingexplained.com/coding/theory/binary-search-algorithm)

Valaki el tudná magyarázni a mögöttes matematikát? Kösz.

python algorithm binary-search
31.01.2016

  • keresés után minden alkalommal 2-vel osztjuk a listát, amíg 1-et nem kapunk. Nem: az Ön által hivatkozott megvalósításban minden iteráció eltávolítja a lista egy elemét a figyelembevételből, majd csökkenti a régiót. az elemtől jobbra vagy balra mindenre érdekes. A konkrétság kedvéért a próbát inkább listakeresésnek (xs[mid_index]) kell tekintenie, nem pedig iterációnak. 31.01.2016

Válaszok:


1

Legyen P(n) a n elemhez szükséges próbák száma. Ekkor felírhatjuk a következő egyenletet:

P(0) = 0
P(n) = 1 + P((n-1)/2)

Magyarázat: Először is nincsenek elemeink – nincs mit tenni. Ezután csinálunk 1 próbát, és marad (n-1)/2 elem (1-et kidobunk, mert most ellenőriztük), így még P((n-1)/2) próbát kell csinálnunk.

Ebből az egyenletből a P(n) eredménye floor(lg(n+1)) lesz. Ellenőrizheti néhány példán (például n=6 és n=7), vagy olvashat a rekurzív egyenletek megoldásáról

31.01.2016
  • A második egyenlet valóban P(n) = 1 + P(n // 2) legyen: vegyük például a n = 6 esetet - egy 'középső' elemet választunk, 2 elemet hagyva az egyik oldalon, 3-at a másikon; a legrosszabb esetben végül erre a 3 elemre redukálunk, tehát azt akarjuk, hogy az egyenlet P(6) = 1 + P(3) legyen. (Az első eset, amikor ez különbséget jelent, a n = 2; nekünk P(2) = 2-nek kellene lennie.) 31.01.2016
  • Azt hiszem, igazad van, de ez más eredményt ad. Talán tényleg hiba van a cikkben? 31.01.2016
  • Szerintem nincs hiba a cikkben. A 1 + P((n-1)/2) használatával olyasmit kap, ami nem ért egyet a cikkben foglaltakkal, amint azt már a P(2) esetében is jeleztem. (A P(2) esetén ceil(log2(3))-t kell kapnia, ami 2, de a definíciójával P(2) = 1.) Ha a (n-1)/2-et n//2-ra módosítja, akkor a definíciója megegyezik a cikkel. A cikk melyik része szerinted hibás? 31.01.2016
  • Köszönöm mindkettőtöknek. Megpróbálom megoldani aP(n) = 1 + P(n/2) rekurzív egyenletet, de valahogy más megoldást kapok. Az n-t behelyettesítem 2^n-nel, és végül P(n) = log2(n) + 1-t kaptam. Bár a különbség nem sok, de megköszönném, ha valaki megmondaná, hogyan oldjam meg. Kösz. 01.02.2016
    • Új anyagok
    A rádiógomb ellenőrzött eseményének használata a jQueryben
    Ebben a cikkben látni fogjuk, hogyan kell dolgozni a jquery választógombbal ellenőrzött eseményeivel. A választógombok HTML gombok, amelyek segítenek kiválasztani egyetlen értéket egy csoportból...
    Körkörös függőségek megoldása terraformban adatforrásokkal – lépésről lépésre
    Mi az a körkörös függőségek Dolgozzunk egy egyszerű eseten, amikor az SQS-sor és az S3-vödör közötti körkörös függőség problémája van egy egymástól függő címkeérték miatt. provider..
    Miért érdemes elkezdeni a kódolást 2023-ban?
    01100011 01101111 01100100 01100101 — beep boop beep boop Világunk folyamatosan fejlődik a technológia körül, és naponta fejlesztenek új technológiákat a valós problémák megoldására. Amint..
    🎙 Random Noise #2  – Örökbefogadás és hit
    az analitika íratlan világának gondozása Szeretné, hogy ezek a frissítések a postaládájába kerüljenek? Iratkozzon fel itt . "Ha önvezető autókat gyártanak, akkor mi miért ne..
    A legrosszabb politika és prediktív modellek májátültetésre jelöltek számára az Egyesült Államokban
    A máj (vagy óangolul lifer) az emberi test legnehezebb belső szervére utal, amely csendesen működik a nap 24 órájában. Mit csinál a máj? 500 feladatot hajt végre a szervezet egészségének..
    5 webhely, amely 2022-ben fejleszti front-end fejlesztői készségeit
    Frontendmentor.io A tényleges projektek létrehozásával a Frontendmentor.io segítséget nyújt a front-end kódolási képességeinek fejlesztésében. A kódolást azután kezdheti meg, hogy..
    Mikor kell használni a Type-t az interfészhez képest a TypeScriptben?
    A TypeScript a JavaScript gépelt szuperkészlete, amely statikus gépelést ad a nyelvhez. Ez megkönnyíti a robusztus és karbantartható kód írását azáltal, hogy a hibákat a fordítási időben..