Algoritmul pentru găsirea primul număr întreg mai mare, cu o-mici (n) complexitate

voturi
0

Am nevoie pentru a scrie un algoritm, care va găsi primul număr întreg, care este mai mare decât x într-o matrice de sortat, în cazul în care numere întregi se pot repeta. Algoritmul ar trebui să aibă complexitatea O (n), în cazul în care o este mică. Care este diferența dintre algoritmii cu O (n) o o (n) dificultate?

Întrebat 20/10/2018 la 13:58
sursa de către utilizator
În alte limbi...                            


3 răspunsuri

voturi
2

Puteți folosind metoda binar de căutare pentru a găsi cel mai mare primul număr întreg de x. Ar fi , în O(log(n)) = small_o(n).

Publicat 20/10/2018 la 14:14
sursa de către utilizator

voturi
1

Așa cum oamenii au arătat în fața mea, vrei să faci o căutare binară. Acest post include, de exemplu, codul:

În piton acest lucru este cel mai ușor cu funcția bisect: https://docs.python.org/2/library/bisect.html

from bisect import bisect_right

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError
Publicat 20/10/2018 la 14:42
sursa de către utilizator

voturi
1

Aici este un foarte bun și în explicația detaliată a mari O vs puțin o notație: Diferența dintre Big-O și Little-O Notația

Cel mai simplu algoritm , dar eficient este binar de căutare după cum sa menționat @OmG, și aici este link - ul pentru a începe: https://en.wikipedia.org/wiki/Binary_search_algorithm

Ideea este destul de simplu: trebuie doar să comparați numărul pe care îl căutați cu elementul de mijloc de matrice, în cazul în care mijlocul este mai mic, atunci numărul tău este evident că trebuie să găsiți pe jumătatea din dreapta, ... jumătate în caz contrar stânga. Te opresti atunci când există doar un singur element.

Publicat 20/10/2018 la 14:22
sursa de către utilizator

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more