Video: Trading Automatico: pensi di diventare ricco senza fare nulla? Devi sapere questo allora .. 2024
Una funzione in matematica è semplicemente un modo per mappare alcuni input per una risposta. Espressa in un modo diverso, una funzione è una trasformazione (basata su operazioni matematiche) che trasforma (mappa) il tuo input in una risposta.
Per determinati valori di input (solitamente indicati con le lettere x o n), si ottiene una risposta corrispondente utilizzando il calcolo matematico che definisce la funzione. Ad esempio, una funzione come f (n) = 2 n ti dice che quando il tuo input è un numero n, la tua risposta è il numero n moltiplicato per 2.
L'uso della dimensione dell'ingresso ha senso dato che questa è un'età critica e la vita delle persone è piena di una quantità crescente di dati. Rendere tutto una funzione matematica è un po 'meno intuitivo, ma una funzione che descrive come un algoritmo mette in relazione la sua soluzione con la quantità di dati che riceve è qualcosa che puoi analizzare senza un supporto hardware o software specifico. È anche facile da confrontare con altre soluzioni, data la dimensione del tuo problema. L'analisi degli algoritmi è davvero un concetto strabiliante perché riduce una serie complessa di passaggi in una formula matematica.
Inoltre, la maggior parte delle volte, un'analisi degli algoritmi non è nemmeno interessata a definire esattamente la funzione. Quello che vuoi veramente fare è confrontare una funzione obiettivo con un'altra funzione. Queste funzioni di confronto appaiono all'interno di un insieme di funzioni proposte che hanno un rendimento scarso se confrontate con l'algoritmo di destinazione. In questo modo, non è necessario collegare i numeri a funzioni di maggiore o minore complessità; invece, ti occupi di funzioni semplici, premade e ben note. Può sembrare approssimativo, ma è più efficace ed è simile alla classificazione delle prestazioni degli algoritmi in categorie, piuttosto che ottenere una misurazione esatta delle prestazioni.
L'insieme di funzioni generalizzate è chiamato notazione Big O, e spesso si incontra questo piccolo insieme di funzioni (messo tra parentesi e preceduto da una maiuscola O >) utilizzato per rappresentare le prestazioni degli algoritmi. La figura mostra l'analisi di un algoritmo. Un sistema di coordinate cartesiane può rappresentare la sua funzione come misurata dalla simulazione RAM, dove l'ascissa (la coordinata x) è la dimensione dell'ingresso e l'ordinata (la coordinata y) è la sua numero risultante di operazioni. Puoi vedere tre curve rappresentate. Le dimensioni dell'input sono importanti. Tuttavia, anche la qualità è importante (ad esempio, quando si ordinano problemi, è più veloce ordinare un input che è già quasi ordinato).Di conseguenza, l'analisi mostra il caso peggiore, f 1 (n), un caso medio, f 2 (n), e un caso migliore, f 3 (n). Anche se il caso medio potrebbe darti un'idea generale, quello che ti interessa davvero è il caso peggiore, perché possono sorgere problemi quando il tuo algoritmo fatica a raggiungere una soluzione. La funzione Big O è quella che, dopo un certo valore
n0
(la soglia per considerare un input grande), risulta sempre in un numero maggiore di operazioni dato lo stesso input rispetto alla funzione del caso peggiore > f1
. Pertanto, la funzione Big O è ancora più pessimistica di quella che rappresenta il tuo algoritmo, quindi, indipendentemente dalla qualità dell'input, puoi essere certo che le cose non possono peggiorare.
Complessità di un algoritmo in caso di input migliore, medio e peggiore.
Molte funzioni possibili possono portare a risultati peggiori, ma la scelta delle funzioni offerte dalla notazione Big O che è possibile utilizzare è limitata perché il suo scopo è di semplificare la misurazione della complessità proponendo uno standard. Di conseguenza, questa sezione contiene solo le poche funzioni che fanno parte della notazione Big O. Il seguente elenco li descrive in ordine crescente di complessità:
La stessa ora, indipendentemente dalla quantità di input fornita. Alla fine, è un numero costante di operazioni, indipendentemente dalla durata dei dati di input. Questo livello di complessità è piuttosto raro nella pratica.
- Complessità logaritmica O (log n): Il numero di operazioni cresce a un ritmo più lento dell'input, rendendo l'algoritmo meno efficiente con piccoli input e più efficiente con quelli più grandi. Un algoritmo tipico di questa classe è la ricerca binaria.
- Complessità lineare O (n): Le operazioni crescono con l'input in un rapporto 1: 1. Un algoritmo tipico è l'iterazione, ovvero quando si esegue la scansione di input una sola volta e si applica un'operazione a ciascun elemento di essa.
- Complessità Linearitmica O (n log n): La complessità è un mix tra complessità logaritmica e lineare. È tipico di alcuni algoritmi intelligenti utilizzati per ordinare dati, come Mergesort, Heapsort e Quicksort.
- Complessità quadratica O (n 2
- ): Le operazioni crescono come un quadrato del numero di input. Quando si ha una iterazione all'interno di un'altra iterazione (iterazioni nidificate, in informatica), si ha una complessità quadratica. Ad esempio, hai un elenco di nomi e, per trovare quelli più simili, confronti ogni nome con tutti gli altri nomi. Alcuni algoritmi di ordinamento meno efficienti presentano tale complessità: ordinamento di bolle, ordinamento di selezione e ordinamento di inserimento. Questo livello di complessità significa che i tuoi algoritmi possono essere eseguiti per ore o addirittura giorni prima di raggiungere una soluzione. Complessità cubica O (n 3
- ): Le operazioni crescono anche più rapidamente della complessità quadratica perché ora si hanno più iterazioni annidate. Quando un algoritmo ha questo ordine di complessità ed è necessario elaborare una modesta quantità di dati (100.000 elementi), l'algoritmo potrebbe funzionare per anni.Quando si ha un numero di operazioni che è una potenza dell'input, è comune fare riferimento all'algoritmo come in esecuzione in tempo polinomiale. Complessità esponenziale O (2 n
- ): L'algoritmo richiede il doppio del numero di operazioni precedenti per ogni nuovo elemento aggiunto. Quando un algoritmo ha questa complessità, anche piccoli problemi possono richiedere per sempre. Molti algoritmi che eseguono ricerche esaurienti hanno una complessità esponenziale. Tuttavia, l'esempio classico di questo livello di complessità è il calcolo dei numeri di Fibonacci. Complessità fattoriale O (n!): Un vero incubo di complessità a causa dell'elevato numero di possibili combinazioni tra gli elementi. Immagina: se il tuo input è di 100 oggetti e un'operazione sul tuo computer richiede 10
- -6 secondi (una velocità ragionevole per ogni computer, oggigiorno), avrai bisogno di circa 10 140 anni per completare correttamente l'attività (una quantità di tempo impossibile dall'età dell'universo è stimata in 10 14 anni). Un famoso problema di complessità fattoriale è il problema del commesso viaggiatore, in cui un venditore deve trovare il percorso più breve per visitare molte città e tornare alla città di partenza.
