Cea mai slabă complexitate în timp a căutării liniare O(n) (Programare, Java, Algoritm, Mare O, Evaluare)

jaymartines a intrebat.

Încerc să scriu un raport în care să evaluez complexitatea în timp a unui algoritm pe care l-am proiectat, știu sigur că complexitatea lui este O(n). Din ceea ce am luat de pe Wikipedia, cel mai bun caz ar fi O(1), dacă am înțeles corect înseamnă că cel mai bun caz este atunci când ArrayList-ul pe care îl folosesc conține un singur element, dar nu înțeleg complet cel mai rău caz, ce înseamnă „O(1) iterativ” și cum se poate întâmpla asta?

Comentarii

  • Complexitatea în cel mai bun caz pentru căutarea liniară este O(1): Ceea ce înseamnă că valoarea pe care o căutați este găsită chiar la primul indice. Complexitatea în cel mai rău caz este O(n), ceea ce înseamnă că valoarea nu a fost găsită în matrice (sau a fost găsită chiar la ultimul index), ceea ce înseamnă că a trebuit să iterăm de n ori pentru a ajunge la această concluzie. –  > Por Mushif Ali Nawaz.
  • Media complexitate este că (în medie) trebuie să căutați elementul în jumătate din listă, deci O(n/2), dar, deoarece constantele sunt eliminate, este O(n), adică același lucru ca în cel mai rău caz. –  > Por Andreas.
  • Poți obține o complexitate în timp O(1) folosind un algoritm bazat pe hash, care, evident, are nevoie de mai mult spațiu pentru a stoca valorile hash… :)… citește despre asta când ai timp. –  > Por Ketan.
2 răspunsuri
Stephen C

Într-un comentariu scrieți::

În cazul meu nu caut un element al listei în particular, ci trebuie să verific dacă atributul fiecărui element este true sau false.

Aceasta nu este o căutare liniară. Căutarea (liniară sau nu) înseamnă a răspunde la întrebarea „există cel puțin un element care se potrivește”. Întrebarea dumneavoastră este „toate elementele se potrivesc”.

Întotdeauna va trebui să mă gândesc la întreaga listă de la primul la ultimul element, deci care ar fi cel mai rău și cel mai bun caz.

Cel mai bun caz este tot O(1). Dacă descoperiți că unul dintre atributele unui element este false, puteți încheia imediat scanarea. Cel mai bun caz este atunci când acest lucru se întâmplă pentru primul element ….

Luați în considerare acest lucru. Verificarea faptului că „toate elementele sunt adevărate” este echivalentă cu verificarea faptului că „NOT (un anumit element este fals)”.

Comentarii

  • Nu sunt sigur că a doua parte este corectă, deoarece nu intră în detaliu în problema sa. El menționează doar că trebuie să verifice dacă fiecare element este adevărat sau fals. El nu menționează că fiecare element trebuie să fie adevărat și că, la atingerea unui element fals, bucla trebuie să se încheie. Poate că el dorește doar să aibă 2 contoare care să adune numărul de elemente adevărate din listă și numărul de elemente false din listă, prin urmare trebuie să parcurgă întreaga listă. Nu cred că a menționat că trebuie să se termine din orice motiv înainte de a ajunge la sfârșit. –  > Por Birdman.
  • Ei bine … poate. (Eu citesc altfel comentariul. Rețineți că el descrie acest lucru ca o căutare, nu ca o operațiune de numărare). Dar să presupunem că atributul elementului poate fi adevărat sau fals sau altceva. Acum, trebuie doar să scanez pentru valoarea „altceva”. Ceea ce este încă O(1) în cel mai bun caz! –  > Por Stephen C.
  • „Nu cred că a menționat că trebuie să se termine din orice motiv înainte de a ajunge la sfârșit.”. Știu că nu are nevoie. Dar aceasta este optimizarea care poate fi făcută pentru operațiile „pentru toți” și „există”. Și este optimizarea la care face aluzie în articolul din Wikipedia. –  > Por Stephen C.
  • Deci, dacă vreți să știți ce fac eu în particular, am o listă de obiecte, fiecare obiect este o persoană, cu atributele nume, prenume, vârstă etc.; vreau să parcurg lista de obiecte, for (Person data : people), if (data.name.equals(„mario”) { Sysout.println(data.name)} –  > Por jaymartines.
  • Deci, nu caut primul „mario”, ci vreau fiecare persoană „mario”, Cu cât este mai lungă lista, cu atât este mai lung timpul de execuție, Dar nu pot identifica notația big O pentru cel mai bun și cel mai rău caz –  > Por jaymartines.
Birdman

Motivul pentru care este O(1) cel mai bun caz nu este JUST pentru o listă cu 1 element (deși ar fi cazul și în acest scenariu). Imaginați-vă că aveți o listă cu 10 numere.

[44,6,1,2,6,10,93,187,33,55]

Să presupunem că executăm căutarea liniară și căutăm numărul întreg 44. Deoarece este primul element din listă, complexitatea timpului nostru este O(1), cel mai bun scenariu, deoarece trebuie să căutăm doar un singur element din întreaga listă înainte de a găsi ceea ce căutăm.

Să ne uităm la o variantă a acestei liste.

[55,6,1,2,6,10,93,187,33,44]

În acest caz, am schimbat primul și ultimul număr. Astfel, atunci când executăm căutarea liniară pentru numărul întreg 44, complexitatea timpului va fi de O(n), cel mai rău caz, deoarece trebuie să parcurgem întreaga listă de n elemente înainte de a găsi elementul dorit (dacă există în listă, în cazul nostru există).

În ceea ce privește „O(1) iterativ” de pe Wikipedia, nu m-aș lăsa confundat. De asemenea, observați că se referă la spațiul complexitatea paginii Wikipedia, și nu performanța complexității temporale. Nu avem nevoie de spațiu suplimentar pentru a stoca nimic în timpul căutării liniare, ci doar comparăm valoarea dorită (cum ar fi 44 în exemplu) cu elementele din matrice, unul câte unul, astfel încât avem o complexitate spațială de O(1).

EDIT: Pe baza comentariului dumneavoastră:

În cazul meu, nu caut un element al listei în mod special.

Rețineți că „Căutarea liniară” este un algoritm special cu scopul specific de a găsi un anumit element dintr-o listă, ceea ce, după cum menționați, NU este ceea ce încercați să faceți. Se pare că nu căutarea liniară este ceea ce căutați. Căutarea liniară are în vedere o matrice/listă și un element dorit. Acesta va returna indexul unde apare elementul dorit în listă, presupunând că acesta există în listă.

Întotdeauna ar trebui să mă gândesc la întreaga listă de la primul la ultimul element.

Din descrierea comentariului dvs., cred că încercați să parcurgeți o listă de la început până la sfârșit, întotdeauna. Acest lucru ar fi O(N) întotdeauna, deoarece parcurgeți întotdeauna întreaga listă. Luați în considerare acest exemplu simplu din Python:

L1 = [1,2,3,4,5,6,7,8,9,10]  #Size n, where n = 10

for item in L1:
    print(item)

Acesta va imprima fiecare element din listă. Lista noastră este de dimensiune n. Deci complexitatea în timp a parcurgerii listei este O(n). Acest lucru se aplică numai dacă doriți să parcurgeți întreaga listă de fiecare dată.

Comentarii

  • Mulțumesc pentru răspunsul rapid, În cazul meu nu caut un element al listei în mod special, ci trebuie să verific dacă atributul fiecărui element este adevărat sau fals (este o listă de obiecte), ar trebui să parcurg întotdeauna întreaga listă de la primul la ultimul element, deci care ar fi cel mai rău și cel mai bun caz? –  > Por jaymartines.
  • @jaymartines – În acest caz, descrierea problemei dvs. ca „căutare liniară” este incorectă. –  > Por Stephen C.
  • @jaymartines Se pare că căutarea liniară ar putea să nu fie ceea ce căutați pentru a îndeplini sarcina. Căutarea liniară ar trebui să primească un element (vom spune X) și o listă/un tablou (vom spune L1). Se pornește de la începutul lui L1 și se parcurge lista unul câte unul. Dacă găsește elementul X în lista L1, returnează rezultatul, de obicei indicele, al elementului X. Ceea ce încercați să faceți este în esență doar o buclă „for each”. Doriți să parcurgeți fiecare element din listă de fiecare dată. Deci, indiferent de situație, parcurgeți n elemente dintr-o listă de n elemente. Deci, cel mai bun & cel mai rău caz este O(n). –  > Por Birdman.
  • @jaymartines Cred că mi-am dat seama ce încerci să realizezi. Ai menționat în postarea ta că analizezi un algoritm proiectat de TINE. Evident că nu ai proiectat căutarea liniară. Cred că ai un algoritm mai mare și încerci doar să identifici care este complexitatea timpului pentru o parte din el, corect? Iar acea porțiune este cea în care doriți să parcurgeți fiecare element dintr-o listă, corect? (ceea ce ați considerat ca fiind o „căutare liniară”, când, de fapt, căutarea liniară este un algoritm complet separat, cu un scop specific).  > Por Birdman.
  • „”Deoarece este primul element din listă, complexitatea timpului nostru este O(1) … Nu, nu cred că acest lucru este corect. Complexitatea în timp a unui algoritm este o caracteristică a performanței generale a algoritmului. Acest termen nu poate fi aplicat unui caz special pentru un algoritm. –  > Por scottb.