Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. Web Development
Code

Algoritmi şi structuri de date

by
Difficulty:BeginnerLength:ShortLanguages:
This post is part of a series called Data Structures Succinctly: Part 1.
Stacks and Queues
The Set Collection

Romanian (Română) translation by Andrei Cornea (you can also view the original English article)

Presupun ca esti un programator. Poate că sunteţi un student nou de informatică sau poate esti un inginer de software-ul experimentat. Indiferent unde vă aflaţi pe acest spectru, indiferent de structurile de date şi algoritmi. Nu doar ca conceptele teoretice, dar ca blocuri utilizate pentru a crea soluţii la problemele de afaceri.

Sigur, poate ştiţi cum să utilizaţi clasa C# lista sau Stack, dar ai înţeles ce se întâmplă sub acoperă? Dacă nu, te face cu adevărat cele mai bune decizii despre care algoritmi şi structuri de date, utilizaţi?

Înţelegerea semnificative de algoritmi şi structuri de date începe cu care au o modalitate de a exprima şi de a compara costurile lor relativă.

Analiza asimptotică

Atunci când vorbim despre măsurarea costurilor sau complexitatea unui algoritm, ceea ce este într-adevăr vorba despre efectuează o analiză a algoritmului când seturi de intrare sunt foarte mari. Analiza ceea ce se întâmplă ca numărul de intrări devine foarte mare este menţionată ca asimptotică analiza. Cum complexitatea schimbarea algoritmului atunci când este aplicat la articole de zece, sau mie, sau zece milioane? Dacă un algoritm se execută în milisecunde cinci cu o mie de elemente, ceea ce poate ne spun despre ceea ce se va întâmpla când se execută cu un milion? Va dura cinci secunde sau cinci ani? Nu ar tine, mai degrabă figura asta înainte de client?

Aceste lucruri conteaza!

Rata de creştere

Rata de creştere descrie cum complexitatea unui algoritm modificări ca dimensiunea intrare creste. Acest lucru este de obicei reprezentat folosind notația Big-O. Mare-O notaţie utilizează un capital O ("comanda") şi o formulă care exprimă complexitatea algoritmului. Formula poate avea o variabilă, n, care reprezinta dimensiunea de intrare. Următoarele sunt unele funcţii ordine comune, vom vedea în această carte, dar această listă nu este deloc completă.

Constanta - O(1)

Un algoritm de O(1) este unul a cărui complexitate este constant indiferent cât de mare este dimensiunea de intrare. "1" nu înseamnă că nu există doar o singură operaţiune sau că operaţiunea durează o cantitate mică de timp. Ar putea dura o microsecundă sau ar putea dura o oră. Ideea este că mărimea de intrare nu influenţează timpul operațiunii ia.

Liniar - O(n)

Un algoritm de O(n) este una a căror complexitate creşte liniar cu mărimea de intrare. Este rezonabil să ne aşteptăm că dacă o dimensiune intrare unul ia cinci milisecunde, o intrare cu o mie de elemente va avea cinci secunde.

Vă poate recunoaşte adesea un algoritm de O(n) privind un mecanism de buclare care accesează fiecare membru.

Logaritmică - O (log n)

Un algoritm de O (log n) este unul a cărui complexitate este logaritmică la dimensiunea. Multe divide şi stăpâneşte algoritmi căderea în acest galeata. Căutare binară copac contine metoda implementeaza un algoritm de O (log n).

Linearithmic - O (n log n)

Un algoritm de linearithmic, sau loglinear, este un algoritm care are o complexitate al O (n log n). Unele divide şi stăpâneşte algoritmi căderea în acest galeata. Vom vedea două exemple când ne uităm la îmbinare fel şi fel de rapid.

Pătratice - O(n^2)

Un algoritm de O(n^2) este unul a cărui complexitate este pătratic la dimensiunea. În timp ce nu întotdeauna evitate, folosind un algoritm patratic este potenţial semn că trebuie să-şi reconsidere algoritm sau date structura de alegere. Algoritmi de pătratice scară bine ca dimensiunea intrare creste. De exemplu, o matrice cu 1000 numere întregi ar necesita 1.000.000 operaţiuni pentru a finaliza. O intrare cu un milion elemente ar lua o bilioane (1,000,000,000,000) operaţiuni. Pentru a pune acest lucru în perspectivă, în cazul în care fiecare operațiune durează o milisecunda pentru a finaliza, un algoritm de O(n^2) care primeşte o intrare de un milion elemente va avea de aproape 32 de ani pentru a finaliza. A face acest algoritm de 100 de ori mai repede ar lua încă 84 de zile.

Când ne uităm la fel de bule, vom vedea un exemplu de un algoritm patratic.

Cel mai bun, mediu şi cel mai rău caz

Când spunem că un algoritm este O(n), ceea ce am cu adevărat spun? Ne spun că algoritmul este O(n) medie? Sau vom descrie cel mai bine sau mai rău caz scenariu?

Ne referim de obicei cel mai rău caz scenariu dacă nu caz comun şi cel mai rău caz sunt foarte diferite. De exemplu, vom vedea exemple în această carte în cazul în care un algoritm este O(1) medie, dar devine periodic O(n) (a se vedea ArrayList.Add). În aceste cazuri voi descrie algoritmul ca O(1) medie şi explica atunci când complexitatea modificări.

Punct-cheie este că spune O(n) nu înseamnă că este întotdeauna n operaţiuni. Ar putea fi mai puţin, dar ar trebui să fie nu mai mult.

Ceea ce ne sunt de măsurare?

Atunci când ne sunt de măsurare algoritmi şi structuri de date, de obicei, este vorba despre unul din două lucruri: cantitatea de timp la care operațiunea produce pentru a finaliza (complexitatea operaţionale), sau cantitatea de resurse (memorie) un algoritm foloseste (complexitate de resurse).

Un algoritm care ruleaza de zece ori mai repede, dar foloseşte zece ori mai multă memorie, ar putea fi perfect acceptabil într-un mediu de server cu cantităţi mari de memorie disponibil, dar nu pot fi adecvate într-un mediu încorporat în cazul în care memoria disponibilă este strict limitată.

În această carte, I se va concentra în principal pe complexitatea operaţionale, dar în secţiunea algoritmi de sortare vom vedea câteva exemple de complexitate de resurse.

Unele exemple specifice de lucruri am putea măsura includ:

  • Operaţii de comparaţie (mai mare decât, mai puţin decât, egal cu).
  • Misiuni şi schimbul de date.
  • Alocări de memorie.

Cadrul operaţiunii efectuate de obicei vă va spune ce tip de măsurare se face.

De exemplu, atunci când se discută complexitatea unui algoritm care caută un element într-o structură de date, aproape sigur vorbim despre operaţii de comparaţie. Căutaţi este în general o operaţiune doar-în-citire, astfel încât nu trebuie să existe nici o nevoie pentru a efectua misiuni sau aloca memorie.

Cu toate acestea, atunci când este vorba de sortarea datelor ar putea fi logic să presupunem că am putea fi vorba despre comparaţii, misiuni sau alocări. În cazurile în care pot exista ambiguitate, eu va indica ce tip de măsură complexitatea se referă de fapt la.

Următorul

Aceasta completează prima parte despre algoritmi şi structuri de date. Apoi, vom trece la lista de legat.

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.