Video: Lucrul cu mai multe foi de calcul și Macro-comenzi în Excel 2007 2024
O funcție în matematică este pur și simplu o modalitate de a mapa unele intrări la un răspuns. Exprimat într-un mod diferit, o funcție este o transformare (bazată pe operații matematice) care transformă (maparea) intrarea dvs. într-un răspuns.
Pentru anumite valori de intrare (de obicei, notate cu literele x sau n), aveți un răspuns corespunzător utilizând matematica care definește funcția. De exemplu, o funcție ca f (n) = 2 n vă spune că atunci când intrarea dvs. este un număr n, este numărul n înmulțit cu 2.
Folosirea dimensiunii intrării are sens, având în vedere că aceasta este o epocă critică și că viețile oamenilor sunt înghesuiți cu o cantitate tot mai mare de date. Făcând totul o funcție matematică este puțin mai puțin intuitivă, însă o funcție care descrie modul în care algoritmul își corelează soluția cu cantitatea de date pe care o primește este ceva pe care îl puteți analiza fără suport hardware sau software. Este, de asemenea, ușor de comparat cu alte soluții, având în vedere dimensiunea problemei dvs. Analiza algoritmilor este un concept minunat, deoarece reduce o serie complexă de pași într-o formulă matematică.
În plus, de cele mai multe ori, o analiză a algoritmilor nu este chiar interesată de definirea precisă a funcției. Ce vrei cu adevărat să faci este să compari o funcție țintă cu o altă funcție. Aceste funcții de comparație apar într-un set de funcții propuse care funcționează prost atunci când sunt contraste cu algoritmul țintă. În acest fel, nu trebuie să conectați numerele la funcții de complexitate mai mare sau mai mică; în schimb, vă ocupați cu funcții simple, premade și bine-cunoscute. Poate suna dur, dar e mai eficient și este similar cu clasificarea performanțelor algoritmilor în categorii, în loc să obțină o măsurare exactă a performanței.
Setul de funcții generalizate se numește notație Big O și întâlniți adesea acest set mic de funcții (puse în paranteze și precedate de o capitală O >) utilizate pentru a reprezenta performanța algoritmilor. Figura arată analiza unui algoritm. Un sistem de coordonate cartezian poate reprezenta funcția măsurată prin simularea RAM, unde abscisa (coordonata x) este dimensiunea intrării și ordonata (coordonata y) numărul de operațiuni rezultate. Puteți vedea trei curbe reprezentate. Dimensiunea intrărilor contează. Cu toate acestea, calitatea contează (de exemplu, atunci când se comandă probleme, este mai rapid să comandați o intrare deja aproape ordonată).În consecință, analiza prezintă un caz mai prost, f 1 (n), un caz mediu f 2 cel mai bun caz, f 3 (n). Chiar dacă cazul mediu ar putea să vă dea o idee generală, ceea ce vă interesează cu adevărat este cel mai rău caz, deoarece problemele pot apărea atunci când algoritmul dvs. încearcă să ajungă la o soluție. Funcția Big O este cea care, după o anumită valoare n0 (pragul pentru a considera o intrare mare), duce întotdeauna la un număr mai mare de operații având aceeași intrare decât funcția celui mai rău caz > f1. Astfel, funcția Big O este chiar mai pesimistă decât cea care reprezintă algoritmul dvs., astfel încât, indiferent de calitatea intrării, puteți fi siguri că lucrurile nu se pot înrăutăți.
Complexitatea unui algoritm în cazul celui mai bun, mediu și cel mai rău caz de intrare.
Multe funcții posibile pot duce la rezultate mai slabe, dar alegerea funcțiilor oferite de notația Big O pe care o puteți utiliza este restricționată deoarece scopul său este de a simplifica măsurarea complexității prin propunerea unui standard. În consecință, această secțiune conține doar câteva funcții care fac parte din notația Big O. Următoarea listă le descrie în ordinea crescătoare a complexității:
Complexitatea constantă O (1):
În același timp, indiferent de cantitatea de intrare pe care o furnizați. În final, este un număr constant de operații, indiferent cât timp sunt datele de intrare. Acest nivel de complexitate este destul de rar în practică.
Numărul de operații crește cu o rată mai mică decât cea de intrare, făcând algoritmul mai puțin eficient cu intrări mici și mai eficient cu cele mai mari. Un algoritm tipic din această clasă este căutarea binară.
- Complexitatea liniară O (n): Operațiile cresc cu intrarea într-un raport de 1: 1. Un algoritm tipic este iterația, care este atunci când scanați o dată intrarea și aplicați o operație fiecărui element al acesteia.
- Complexitatea liniaritmică O (n log n): Complexitatea este o combinație între complexitatea logaritmică și liniară. Este tipic unor algoritmi inteligenți folosiți pentru a comanda date, cum ar fi Mergesort, Heapsort și Quicksort.
- Complexitatea patratică O (n 2
- ): Operațiile cresc ca un pătrat al numărului de intrări. Când aveți o iterație într-o altă iterație (iterații imbricate, în știința informaticii), aveți complexitate patratică. De exemplu, aveți o listă de nume și, pentru a găsi cele mai similare, comparați fiecare nume cu toate celelalte nume. Alți algoritmi de ordonare mai puțin eficienți prezintă o astfel de complexitate: sortarea bulei, sortarea selecției și sortarea inserției. Acest nivel de complexitate înseamnă că algoritmii dvs. pot funcționa cu ore sau chiar zile înainte de a ajunge la o soluție.
- Complexitatea cubică O (n 3 ): Operațiile cresc chiar mai repede decât complexitatea cuadratoare, deoarece acum aveți mai multe iterații imbricate. Atunci când un algoritm are această ordine de complexitate și trebuie să procesați o cantitate modestă de date (100, 000 de elemente), algoritmul dvs. poate rula de ani de zile.Când aveți o serie de operații care reprezintă o putere a intrării, este comun să vă referiți la algoritm ca
- care rulează în timp polinomial. Complexitatea exponențială O (2 n ): Algoritmul ia de două ori numărul operațiilor anterioare pentru fiecare element adăugat nou. Când un algoritm are această complexitate, chiar și problemele mici pot dura pentru totdeauna. Mulți algoritmi care efectuează căutări exhaustive au complexitate exponențială. Cu toate acestea, exemplul clasic pentru acest nivel de complexitate este calculul numerelor Fibonacci.
- Complexitatea factorilor O (n!): Un adevărat coșmar de complexitate datorită numărului mare de combinații posibile dintre elemente. Doar imaginați-vă: dacă intrarea dvs. este de 100 de obiecte și o operațiune pe computer durează 10 -6 secunde (o viteză rezonabilă pentru fiecare calculator, astăzi), veți avea nevoie de aproximativ 10
- 140 pentru a finaliza cu succes sarcina (un timp imposibil de la vârsta universului este estimat la 10 14 ani). O problemă faimoasă a complexității factoriale este problema vânzătorilor care călătoresc, în care un vânzător trebuie să găsească cel mai scurt traseu pentru a vizita multe orașe și pentru a reveni la orașul de plecare.
