Wondershare EdrawMind
Galleria mappe mentale Analisi e progettazione di algoritmi
- 11
Analisi e progettazione di algoritmi
Una mappa mentale sull'analisi e la progettazione di algoritmi Un algoritmo è un calcolo che soddisfa le condizioni di terminazione, certezza, fattibilità, input e output. Non importa quale algoritmo viene utilizzato per trovare la soluzione ottimale, deve essere chiaro quale sia la soluzione ottimale.
Modificato alle 2023-10-28 17:00:08
- Microbiologia medica Infezione batterica e immunità
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
- teoria cinetica dei gas
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
- Breve História do Tempo
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
Analisi e progettazione di algoritmi
- Microbiologia medica Infezione batterica e immunità
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
- teoria cinetica dei gas
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
- Breve História do Tempo
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
- Consigliato per te
- Profilo
Sfide e cracking delle informazioni tramite scatole nere algoritmiche focus sul diritto di interpretare gli algoritmi
- 9
Compilazione dei contenuti di comunicazione dell'algoritmo di raccomandazione ufficiale Douyin
- 8
Comprendere i risultati di controllo di base degli algoritmi e le loro applicazioni nella vita
- 8
![[408]Strutture dati e algoritmi](https://edrawcloudpublicus.s3.amazonaws.com/work/5594747/2024-6-4/1717464089/thumb.png?x-oss-process=image/resize,w_300,m_lfit)
Analisi e progettazione di algoritmi
capitolo 1 introduzione
Un algoritmo è un calcolo che soddisfa le seguenti condizioni
Scopo: risolvere problemi
Terminabilità
certezza
fattibilità
accedere
produzione
calcolare
给定计算模型机械的执行的规则或计算步骤序列被称为计算
一个计算机程序是一个计算
Il calcolo non è un algoritmo
domanda
Definisce la relazione tra input e output
L'algoritmo Autumn Festival è un problema completo, non un semplice esempio di problema
Algoritmo di analisi
Correttezza dell'algoritmo: termina per tutti gli input e produce output corretti
Algoritmo errato: non termina o produce un output errato per un input
Correttezza degli algoritmi approssimativi/stocastici: termina per tutti gli input, produce soluzioni approssimativamente corrette o un numero limitato di soluzioni errate
Motivo della prova di correttezza
I programmi di debug non possono dimostrare che non ci siano errori
metodo
Termina su tutti gli input
Ogni input ha l'output corretto
complessità dell'algoritmo
Scopo: analizzare la quantità di risorse richieste dall'algoritmo per diversi input
Complessità temporale, complessità spaziale, numero di input e output, ecc.
funzione della dimensione di input
Dimensione input: dimensione (α)
Complessità temporale dell'istanza: il numero di operazioni maggiormente necessarie per produrre un risultato per un input specifico
Complessità temporale di uno specifico input
Complessità dello spazio delle istanze
ingresso specifico
空间复杂性，对输入产生结果所需要的存储空间大小
是输入大小的函数S(n)
La peggiore complessità del momento
complessità minima dell’algoritmo
complessità media dell’algoritmo
Probabilità di accadimento moltiplicata per la somma di tutte le possibilità di complessità
Modello di analisi algoritmica
modello ad accesso casuale
Modello multiprocessore parallelo
Analisi della complessità temporale
Non è che un programma impieghi molto tempo per risolvere un problema, ma il tempo aumenta molto rapidamente quando la portata del problema si espande.
Complessità temporale a livello costante
Analisi della complessità temporale dell'algoritmo di inserimento diretto
Quando leggi il numero k-esimo, confrontalo positivamente con il numero precedente,
Analisi della correttezza degli algoritmi
metodo invariante del ciclo
Invariante di ciclo P: i dati e le strutture dati su cui si opera hanno proprietà chiave
Ad esempio, in un algoritmo di ordinamento, la proprietà secondo cui l'ordine dei numeri non cambia può essere utilizzata come invariante del ciclo.
inizializzazione del ciclo
Passaggi del ciclo
ciclo terminato
algoritmo di progettazione
dividere e conquistare
programmazione dinamica
algoritmo avido
algoritmo di ricerca degli alberi
Divisione dei problemi
Macchina di Turing
La macchina di Turing deterministica risolve il problema P in tempo polinomiale
Problemi NP risolvibili con una macchina di Turing incerta in tempo polinomiale
Le macchine di Turing incerte non possono più essere Non-NP
sottoargomento
Capitolo 2 Nozioni di base di matematica
2.1 Calcolo dell'ordine della funzione di complessità
L'insieme di funzioni dello stesso ordine f(x)=θ(g(x)) dove l'insieme di funzioni è: θ(g(x)) stretto
Il limite superiore della funzione di ordine inferiore f(n)=0(g(n)) può essere un limite superiore di ordine inferiore rispetto a
Funzione di ordine superiore f(n)=Ω(g(n)) caso migliore con limite inferiore
Non può spiegare la relazione tra le dimensioni, può solo spiegare la relazione di classe; una funzione di ordine superiore non è necessariamente maggiore del suo limite inferiore, specialmente una funzione di ordine superiore [non una funzione strettamente di ordine superiore];
θ(g(n))⊆0(g(n)) f(n)=O(n^k ) Limite polinomiale
Funzione strettamente di ordine inferiore con limite superiore ma non con limite stretto f(n)=o(g(n))
f(n)=o(g(n))⇒(lim)┬(n→∞) f(n)/g(n) =0
Funzione strettamente di ordine superiore con limite inferiore ma non con limite stretto f(n)=ω(g(n))
f(n)=ω(g(n)) se e solo se g(n)=o(f(n))
f(n)=ω(g(n))⇒(lim)┬(n→∞) f(n)/g(n) =∞
proprietà dell'ordine di una funzione
La transitività include i cinque precedenti
La riflessività include i primi tre
Simmetria strettamente legata
antisimmetria
f(n)=0(g(n)) se e solo se g(n)=Ω(f(n))
f(n)=o(g(n)) se e solo se g(n)=ω(f(n))
Il significato dell'ordine delle funzioni nelle formule matematiche
2.2 Stima e limiti di somma
somma lineare
serie
Limiti per la somma diretta
sottoargomento
sottoargomento
2.3 Le equazioni ricorsive utilizzano se stesse per definirsi
Tre metodi principali per risolvere equazioni ricorsive
Sostituzione Indovina Induzione Matematica
Iterare e convertire in una somma, stimare la somma
Teorema principale
sottoargomento
Capitolo 3 Algoritmi di ordinamento e dividi et impera
3.1 Principio del divide et impera
fase di progettazione
Punti: i sottoproblemi potrebbero non essere gli stessi Dividere il tempo D(n)
Governance: risolvere ogni sottoproblema aT(n)
Somma: combina soluzioni ai sottoproblemi C(n)
Complessità temporale totale: T(n) = a(T(n/b)) D(n) C(n)
fase di analisi
Costruisci equazioni ricorsive
Risolvere
3.2 Algoritmo di ordinamento basato sul divide et impera
Il compito principale dell'ordinamento rapido è eseguire l'algoritmo di partizionamento e conoscere le condizioni al contorno
Limite inferiore per il problema di ordinamento
3.3 Mediana e statistiche d'ordine
principio di riduzione
Ad esempio, cerca per metà
Seleziona la domanda
3.4 Trova la coppia di punti più vicina
Metodi di divisione e fusione per ridurre f(n)
Algoritmo spaziale unidimensionale
Ordina prima
algoritmo divide et impera
punto
regola
E
Algoritmo spaziale bidimensionale
3.5 Ordinamento in tempo lineare
Conteggio
Utilizza tre array A, B e C
L'idea generale: input array-A, output array: B, conteggio array: C [base dell'array è l'intervallo di valori di A [0-k [valore massimo in A]]] (requisito: A deve essere un array di numeri interi)
[Nota] Utilizzare la struttura a secchiello quando il consumo di spazio è elevato.
I problemi
A[i] è un numero intero
E l'intervallo di valori dell'array di input 0-k deve essere più piccolo, altrimenti l'efficienza sarà notevolmente ridotta.
Durante il processo di ordinamento, sono richiesti uno spazio di conteggio di lunghezza massima e uno spazio di uscita ausiliario di lunghezza len. Questo spazio è relativamente grande e la complessità dello spazio è O(len max).
Complessità temporale: O(nk)
Radix
Caratteristiche
stabile
Ordina dal più basso al più alto
algoritmo
Requisiti di input: matrice di numeri interi con lo stesso numero di cifre d
Complessità temporale: O(d(n k[intervallo di valori di input, l'impatto è relativamente piccolo e può essere ignorato]))
Problema: d è troppo grande
Esteso utilizzando un algoritmo divide et impera
Dividere l'array con b cifre in b/r e prendere tutti i dati con r cifre verso l'alto. L'intervallo di valori di ciascun dato è 0-2^r-1
Ordina utilizzando il conteggio
Il valore ottimale di r: lgn arrotondato per difetto
Nota: può essere utilizzato quando r non è grande.
Smistamento del secchio
Un presupposto del bucket sorting: l'input è distribuito in modo indipendente e uniforme tra 0-1 [condizioni previste per raggiungere la linearità]
Idea per l'ordinamento del secchio
Dividere 0-1 in secchi di dimensioni uniformi
L'input è ordinato in bucket
Ordinamento dei dati in bucket
Elenca tutti i dati ordinati in ciascun bucket
Complessità temporale: limite stretto n
Alcuni criteri per giudicare gli algoritmi
stable：按照输入顺序合理的排序输出
in-place：没有另外开辟空间
3.6 Trova lo scafo convesso
definizione del problema
Ingresso: una raccolta di punti sul piano, uscita scafo convesso
natura
Per un poligono convesso P, i lati che collegano due punti qualsiasi in P sono tutti all'interno di P.
Algoritmo di Graham-Scan
In senso antiorario, ordinati per dimensione dell'angolo polare
Ruota a sinistra
Avviso
I valori massimo e minimo di xy sono tutti sullo scafo convesso. Innanzitutto, determina uno dei punti come punto di partenza, traccia una linea orizzontale e attraversa i punti sopra iniziando da questa linea orizzontale [viene selezionato il punto più piccolo]
pseudocodice
Trova il punto in Q con il valore più piccolo della coordinata y
Ordina i punti rimanenti in Q in senso antiorario
Spingere nella pila S
Se la commissione di composizione si sposta a sinistra, fai uscire l'elemento in cima alla pila
Complessità temporale: f(n)=0(n logn)
Analisi di correttezza: invariante del ciclo [Prima di elaborare un determinato nodo, lo stack S memorizza CH (Qi-1) dal basso verso l'alto]
algoritmo divide et impera
Condizioni al contorno
punto
Diviso in Ql, Qr
regola
E
Basta eseguire Graham-Scan sulla sequenza unita
Come unire le sequenze
3.7 FFT in trasformata veloce di Fourier
3.8 Moltiplicazione di numeri interi
Ottimizzare la fase di divisione per ridurre a
Definizione del problema: Input - numeri interi binari di n bit X e Y, output - il prodotto di X e Y
capitolo 4 Algoritmo di programmazione dinamica
Riepilogo dell'algoritmo
C'è una sensazione di esaurimento
就是罩子问题和服问题之间的关系之后再使用穷举的方法最后选定最小值作为最优解
注意：覆盖所有情况
4.1 Elementi di programmazione dinamica
Motivo: se i sottoproblemi non sono indipendenti l'uno dall'altro, il metodo del punteggio calcolerà ripetutamente i sottoproblemi comuni, il che è molto inefficiente.
Scopo: Problema di ottimizzazione - Il problema di ottimizzazione consiste nel fornire una funzione di costo, in Cerca nello spazio risolutivo del problema la soluzione ottimale con costo minimo o massimo
I problemi di programmazione dinamica sono un approccio comune per risolvere problemi di ottimizzazione
Definizione: il problema originale è diviso in una serie di sottoproblemi [numero di livelli polinomiali]
Risolvere i sottoproblemi dal basso verso l'alto
Algoritmo divide et impera top-down
Ambito di applicazione: un tipo di problema che può essere risolto come sottoproblemi riutilizzabili
Condizioni d'uso
Sottostruttura ottimizzante: quando la soluzione ottima di un problema contiene la soluzione ottima di un sottoproblema, diciamo che questa Un problema ha una sottostruttura di ottimizzazione.
Sottoproblemi sovrapposti: durante il processo di soluzione del problema, le soluzioni a molti sottoproblemi verranno utilizzate più volte.
Quando non ci sono sovrapposizioni, usa semplicemente “dividi et impera”, altrimenti dovrai creare ulteriore spazio di archiviazione.
Fasi di progettazione dell'algoritmo
– Analizzare la struttura della soluzione ottima [quali sottoproblemi sono composti da soluzioni ottime, basta andare alle condizioni al contorno] – Definire ricorsivamente il costo della soluzione ottima – Dividere ricorsivamente i sottoproblemi fino a renderli indivisibili – Risolvere ciascun sottoproblema dal basso verso l’alto – Calcola il costo della soluzione di ottimizzazione e salvalo – Ottenere informazioni per costruire la soluzione ottimale – Costruire una soluzione ottimale sulla base delle informazioni utilizzate per costruire la soluzione ottimale
4.2 Moltiplicazione di catene di matrici
Definizione del problema: input matrice p_i-1*p; output il metodo per calcolare il costo minimo
Moltiplicazione di matrici
Soddisfatta la legge associativa, ordini di calcolo diversi avranno costi diversi
Utilizzare metodi di programmazione dinamica
Presentano sottoproblemi sovrapposti
Definire ricorsivamente il costo della soluzione ottima
sottoargomento
Soluzione estesa: è possibile utilizzare il metodo di memorizzazione e il punteggio può essere trasformato in una programmazione dinamica.
4.3 Sottosequenza comune più lunga
definizione del problema
risoluzione dei problemi
⚫ Analisi strutturale della soluzione ottimizzata ⚫ Stabilire l'equazione ricorsiva dei costi per la soluzione ottimale ⚫ Dividere i sottoproblemi ricorsivamente ⚫ Calcola il costo della soluzione ottimizzata dal basso verso l'alto e registra le informazioni di costruzione della soluzione ottimizzata ⚫Soluzione di ottimizzazione della costruzione
Analisi ottimizzata della sottostruttura
i-esimo prefisso: Xi
Ottimizza la sottostruttura
È conveniente utilizzare questo metodo per una soluzione ricorsiva
Tre prove dirette
Sovrapposizione di sottoproblemi, numero di problemi che devono essere elaborati (al massimo mn sottoproblemi)
È meglio coprire tutte le situazioni
Per facilitare il calcolo delle condizioni al contorno
Se le condizioni al contorno sono scomode da calcolare, sarà necessario al massimo un tempo O(m) o O(n) per calcolare i confini.
Divisione del problema: utilizzare le condizioni definite sopra, ovvero le condizioni definite in precedenza per la ricorsione
Calcolare il costo della soluzione di ottimizzazione dal basso verso l'alto e quindi risolverlo verso il basso in base alla soluzione di cui sopra.
Infine, risolvi dal basso verso l'alto e risolvi secondo il simbolo della soluzione ottima contrassegnato da B. La soluzione ottenuta è l'inversione della soluzione finale.
Pseudocodice: la soluzione viene trovata per righe e le frecce vengono utilizzate per la ricerca dal basso verso l'alto.
Complessità temporale: O(mn) [numero di sottoproblemi], dove il tempo per costruire la soluzione ottima è O(m n)
Complessità spaziale O(mn)
Strategia di ottimizzazione dello spazio: puoi progettare C solo in due righe e m colonne o qualcosa del genere
4.4 0/1 problema con lo zaino
definizione del problema
Sviluppa una strategia di imballaggio che massimizzi il valore degli articoli nella borsa senza renderli sovrappeso
Analisi preliminare: ci sono due opzioni per ogni articolo, installare o non installare; il costo di calcolo del piano di installazione e rimozione è n [se viene calcolato il valore/tazza da tè, utilizzare il tempo costante per confrontare per ottenere il valore massimo]
Il costo totale del calcolo è O(n2^n)
np problema completo
risoluzione dei problemi
Analisi strutturale della soluzione ottimizzata
Sovrapposizione di sottoproblemi: quando i pesi degli elementi sono gli stessi ed entrambi sono 1, ci sarà un gran numero di sottoproblemi sovrapposti.
Non adatto all'algoritmo “dividi et impera” [puoi provare a utilizzare la memorizzazione]
definizione del problema
Stabilire un'equazione ricorsiva che ottimizzi il costo della soluzione
Definire la matrice dei costi m;
m[i,j]
i:起始的、计算子问题优化解的代价的矩阵时间
j:指的是包的容量
Riepilogo delle equazioni ricorsive
Sottoproblema di partizionamento ricorsivo
Cosa devi sapere per calcolare m[i,j]
Calcolare il costo della soluzione ottimizzata dal basso verso l'alto e registrare le informazioni di costruzione della soluzione ottimizzata
Costruisci una soluzione di ottimizzazione
Calcolo del costo totale: algoritmo pseudopolinomiale
Ci sono quattro situazioni in totale
4.5 Albero binario di ricerca
definizione del problema
Definizione dell'albero di ricerca binario
Influisce sul costo complessivo delle query dell'albero di ricerca: la forma dell'albero e la probabilità di query del nodo
valore atteso dell'albero
I nodi con numero dispari sono nodi foglia
I nodi con numeri pari sono nodi interni
Valore di costo atteso dell'albero E(T).
Il valore del costo è correlato alla profondità dell'albero e all'incremento del costo.
Il nodo radice deve essere un numero pari
risoluzione dei problemi
Analisi strutturale della soluzione ottimizzata
Sottostruttura e prova ottimizzate
Il valore del contributo del sottoalbero: la posizione del sottoalbero è fissa, la sua probabilità è fissa e la sua differenza di contributo è la stella solitaria.
Incremento della contribuzione: probabilità * differenza di profondità
Utilizzare sottostrutture di ottimizzazione per costruire soluzioni ottimali
sovrapposizione dei sottoproblemi
Stabilire un'equazione ricorsiva che ottimizzi il costo della soluzione
Stabilire l'equazione ricorsiva dei costi di ricerca per la soluzione ottimale
Condizioni al contorno e altre considerazioni
tutto coperto
Formula: Probabilità (incremento del costo) [sottoalbero sinistro sottoalbero destro]
W: Incremento; E: Costo previsto; P: Probabilità
Formula di calcolo ricorsivo incrementale
W[i,j] = w(i,j-1) pi pj = w(i,r-1) w(r 1,j) pr
Sottoproblema di partizionamento ricorsivo
Calcolare il costo della soluzione ottimizzata dal basso verso l'alto e registrare le informazioni di costruzione della soluzione ottimizzata
Costruisci una soluzione di ottimizzazione
4.6 Distanza minima di modifica
definizione
Conversione tra due stringhe
Contiene solo tre operazioni: inserimento di caratteri, eliminazione di caratteri e sostituzione di caratteri [ognuna conta come operazione di base]
L'allineamento dei personaggi influisce sull'efficienza
Risolvere
Analisi strutturale della soluzione ottimizzata
Proprietà della distanza minima di modifica
Non sovrapposte: qualsiasi personaggio può eseguire al massimo un'operazione
indipendenza dell'ordine
simmetria
stringa estesa vuota
sovrapposizione dei sottoproblemi
Stabilire un'equazione ricorsiva che ottimizzi il costo della soluzione
Quattro situazioni
Condizioni al contorno
Innanzitutto è necessario considerare le condizioni al contorno come condizioni richieste per il calcolo iniziale.
Algoritmi e complessità algoritmica
Complessità temporale O(mn)
Complessità spaziale: O(mn)
Ottimizza la struttura dello spazio
Sottoproblema di partizionamento ricorsivo
Calcolare il costo della soluzione ottimizzata dal basso verso l'alto e registrare le informazioni di costruzione della soluzione ottimizzata
Costruisci una soluzione di ottimizzazione
Problema di discriminazione della distanza di modifica minima
applicazione
字符串的相似度查询
definizione
input Output
analizzare
La distanza minima di modifica non è inferiore al valore assoluto della lunghezza dei due
Complessità
Due situazioni che non richiedono calcoli
La differenza di lunghezza è maggiore della soglia decisionale di input
È necessario che il calcolo utilizzi il valore del risultato sopra maggiore di 2
complessità spaziale
O(min{m,n}t): può essere ottimizzato
O(t)
complessità temporale
O(min{m,n}t)
Ogni riga/colonna può calcolare al massimo 2*t 1
algoritmo avido capitolo5
La differenza rispetto ai due algoritmi precedenti
子主题
贪心算法：原问题进行选择获取剩余子问题直至子问题为空
delicato
前面两种：原问题划分为子问题，繁重，自底向上
5.1 Principi fondamentali
concetto di base
Algoritmi approssimati, algoritmi euristici
Soluzione ottimale locale, la scelta migliore al momento
esempio
Problema di cambio moneta
Problema di programmazione regionale
utilizzo
Risolvere problemi di ottimizzazione
Idea base
Un algoritmo per risolvere un problema di ottimizzazione consiste in una serie di passaggi, ciascuno dei quali prevede una serie di scelte per effettuare la scelta migliore al momento.
Spero di raggiungere la soluzione ottimale globale
Provalo passo dopo passo, quindi sovraccarica e prova altre cose per trovare l'algoritmo avido
Avvicinarsi gradualmente o addirittura raggiungere finalmente la soluzione ottimale
Esempio
Condizioni per generare soluzioni ottime
Ottimizza la sottostruttura
Avido selettivo
Induzione
Riepilogare i passaggi dell'algoritmo o riepilogare il problema
Ogni passaggio è migliore di altri algoritmi e produce una soluzione ottimale
La soluzione per ogni passaggio incluso non deve necessariamente essere una buona soluzione per il passaggio incluso
scambio di argomenti
Più conveniente
Con la premessa di ottimalità invariata, sostituire gradualmente da una soluzione ottima per ottenere infine la soluzione dell'algoritmo greedy.
Confrontare
fasi di progettazione
fasi di progettazione
algoritmo di selezione avida
sottoproblema rimanente
bisogno di prove
对于贪心选择来说，所求解的问题具有优化子结构
对于贪心选择算法莱说，具有Greedy选择性
5.2 Problemi di selezione delle attività
definizione del problema
risoluzione dei problemi
Progettare un metodo di selezione goloso
Analisi strutturale della soluzione ottimizzata
Prova selettiva golosa
Lemma 1
Dimostrazione della selettività golosa
[Nota] È necessario chiarire quali sono le condizioni per la soluzione ottimale In questo problema, la soluzione ottimale è l'attività più coerente Dipende dalla quantità e dalle caratteristiche di compatibilità
Lemma 2: Ottimizza la sottostruttura
prova per contraddizione
Lemma 3
progettazione dell'algoritmo
Analisi della complessità degli algoritmi
5.3 Codifica di Huffman
definizione del problema
codifica binaria dei caratteri
codifica a lunghezza fissa
codifica a lunghezza variabile
codifica del prefisso
definizione
albero di codifica
Il costo della codifica degli alberi: il costo è la somma prevista della profondità
C: set di caratteri
B: somma dei costi
F: frequenza
Pensieri avidi
Selezionare ciclicamente i due nodi con la frequenza più bassa per generare un sottoalbero fino a formare un albero
risoluzione dei problemi
Progettare un metodo di selezione goloso
Metodo di scelta
La struttura del sottoproblema rimanente
Analisi strutturale della soluzione ottimizzata
Lemma 1: Prova di sottostruttura ottimizzata
Lemma 2: La posizione più profonda, i due caratteri della lettera di nomina minima, la stessa lunghezza massima
avida selettività
Ottimizza l'albero dei prefissi per contenere la lunghezza massima di due nodi alla stessa profondità
Prova selettiva golosa
progettazione dell'algoritmo
Analisi della complessità degli algoritmi
5.4 Albero di copertura minimo
definizione del problema
Algoritmo di Kruskal
progetto
Ottimizza la struttura della soluzione
sottoproblema rimanente
operazione di restringimento
operazione di espansione
Prova della sottostruttura ottimizzata
Avido selettivo
Complessità algoritmica
correttezza dell'algoritmo
Algoritmo di Prim
progetto
Ottimizza la struttura della soluzione
Avido selettivo
Complessità algoritmica
riepilogo
Algoritmo generico
telaio
Idea base
Descrizione dell'algoritmo
avida selettività
definizione
Taglia(S,V-S)
Taglio incrociato
Rispettare il set di taglio del bordo A
Attraverso il bordo chiaro del Taglio
Teorema 1
Kruskal: trova bordi leggeri attraverso il taglio che seguono A [contiene una serie di componenti connessi] e punti non inclusi in A
Algoritmo di Prim
revisione
Tempo minimo di completamento 5.5 Pianificazione minima Mackspan
definizione del problema
algoritmo di approssimazione
Analisi di performance
capitolo 6 analisi di ammortamento
Fondamentale
Idea base
Operazioni sullo stack: ignora le strutture dei dati e le relazioni tra le operazioni
Metodo di analisi ammortizzato
Scopo: Analizzare il limite superiore del costo di n operazioni su una data struttura dati
Il costo di ciascuna operazione viene analizzato equamente attraverso il costo totale [limite superiore]
Ciò che viene determinato è un limite superiore, non una probabilità
metodo di aggregazione
media
metodi contabili
Pagamento anticipato [associato all'oggetto dati, il credito dell'oggetto dati]
Metodo dell’energia potenziale
Potenziale accumulato [associato all'intera struttura dati, energia]
metodo di aggregazione
analizzare
分析过程中要精细化，注意每个操作之间的关联
用数据对象上小的操作代价来来预付之后的大的操作代价
Operazioni correlate
比如multipop的多次是因为前面多次的push，所以需要push操作为他负责
Principio: a diverse operazioni viene assegnato lo stesso costo
La somma di tutte le operazioni, su ciascun elemento di n
contatore binario
Un totale di bit lgn
metodi contabili
principio
Pagamento anticipato [associato all'oggetto dati, il credito dell'oggetto dati]
Principio di selezione: il credito memorizzato nella struttura dati non è negativo
Esempio
analizzare
分析过程中要精细化，注意每个操作之间的关联
用数据对象上小的操作代价来来预付之后的大的操作代价
Operazioni correlate
比如multipop的多次是因为前面多次的push，所以需要push操作为他负责
Operazioni sullo stack
spingere, pop, multipop
Ogni oggetto verrà espulso al massimo una volta dopo essersi alzato
Prova del limite superiore:
contatore binario
Imposta su 0 Imposta su 1
Operazione principale: impostata su 0
Metodo dell’energia potenziale
C'è anche la prova finale relativa al limite superiore.
可以使用放缩
实际的代价小于一个值
或者平摊大于
或者都有
principio
esempio
pila
Definizione di energia potenziale
Addizione binaria
messa a fuoco
势能定义
È meglio definire il numero totale di oggetti incrementati da piccole operazioni
比如说是栈：pop，占中总的对象数目
二进制加法：1的个数
使得总势能大于等于0
就是在每一次操作之后势能都是大于0的
大操作小操作
messa a fuoco
分清楚谁是大操作，谁是小操作
用小的操作代价来来预付之后的大的操作代价
Analisi dell'ammortamento della tabella dinamica
concetto
Operazioni supportate da tabelle dinamiche
Struttura dei dati: utilizzare un array per implementare una tabella dinamica
Fattore di carico: non inferiore a una costante
esprimere
tavoletta]
numero[T]
taglia[T]
espansione e contrazione
Espansione dinamica della tabella
Analisi di aggregazione
Condizioni di analisi e analisi fine
metodi contabili
Costo effettivo dell'operazione di inserimento
propri risparmi per l’espansione
Espansione: grande operazione
Inserisci: piccole operazioni
Dategli il primo oggetto corrispondente senza deposito.
Costo per l'inserimento
Analisi energetica potenziale
Riduzione delle tabelle dinamiche
Il tempo necessario per bufferizzare la tabella
Metodo dell’energia potenziale
Quando l'operazione principale è completata, l'energia potenziale è almeno 1
Man mano che la chiave primaria per le piccole operazioni si avvicina al momento in cui sono necessarie operazioni di grandi dimensioni, l’energia potenziale aumenta gradualmente.
Trai forza per le grandi operazioni
Quando verrà raggiunto il punto chiave, sarà l’energia potenziale necessaria per le grandi operazioni.
relazione
之间有一个二倍
1/4的关系
num在大操作之后是size的一半
Le grandi operazioni sono operazioni di contrazione ed espansione 3
而前面的小操作改变的都是num
势能在小操作的过程中一定是增加的需要注意
Il totale deve aumentare durante la piccola operazione! ! ! ! ! ! ! !
Nota: indipendentemente dall'algoritmo utilizzato per trovare la soluzione ottimale, deve essere chiaro quale sia la soluzione ottimale.