Big-O quando il valore numerico del caso peggiore è noto

Question

Big-O quando il valore numerico del caso peggiore è noto

#1 da (3 voti)
#2 da (1 voti)
#3 da (0 voti)

0

Se ho un algoritmo e una parte di esso ha un valore numerico noto nel caso peggiore, che è ragionevolmente piccolo rispetto al resto del problema, è ok sostenere che la parte sia O (1)?

es. Se parte dell'algoritmo prevede la costruzione di un elenco di caratteri collegati da una stringa, dove la stringa può contenere ciascuno dei caratteri ASCII al massimo una volta, so che il caso peggiore è costruire un elenco collegato di 127 nodi da una stringa che è 127 caratteri. Va bene argomentare quella parte come O (1)?

complexity big-o

posta Kal 06.09.2017 - 11:59

fonte

3 risposte

Leggi altre domande sui tag complexity big-o

Node.js script const variabili in SCREAMING_SNAKE_CASE o camelCase Modo corretto per informare la violazione delle regole aziendali durante l'analisi JSON

score 3 · Answer 1

Sì, non appena è noto un limite superiore assoluto, l'algoritmo ha una complessità costante.

La complessità algoritmica riguarda solo il modo in cui l'algoritmo scala per dimensioni di input arbitrariamente grandi: quanto tempo occorrono per dieci, mille e un trilione di elementi? Poiché il tuo algoritmo è definito solo fino a una certa dimensione massima, questo ridimensionamento non è molto pertinente.

Quando si analizza la complessità di Big-O, questo argomento di input massimo è spesso molto conveniente. Ad esempio, generalmente si assume che la moltiplicazione e l'addizione siano operazioni O (1). Ma ciò vale solo per tipi di dati a larghezza fissa che sono spesso sufficienti nella pratica. Non è valido per le operazioni di precisione arbitraria / bignum, dove l'aggiunta avrà complessità O (log n) (o O (n) per il numero di bit).

Non è sempre corretto ignorare completamente il Big-O anche quando c'è una dimensione massima. Se l'algoritmo mostra proprietà di ridimensionamento significative all'interno del dominio in cui è definito, dovrebbe essere soggetto ad analisi. Ad esempio, gli algoritmi di O (exp n) potrebbero non essere fattibili per qualsiasi cosa tranne le dimensioni di input a una sola cifra, quindi un limite superiore a migliaia è completamente irrilevante in quanto non verrà mai raggiunto. Allo stesso modo, l'argomento secondo cui tutti i programmi sono O (1) perché i computer reali hanno una memoria finita e sono quindi limitati è specioso: di solito sentirai gli effetti di Big-O molto prima di raggiungere quel limite.

score 1 · Answer 2

No, non accetterei un (basso) limite sui possibili input come argomento per chiamare quella parte O (1).

D'altra parte, se questo è parte di un algoritmo più grande che non ha lo stesso limite sull'input del caso peggiore, allora l'algoritmo totale è O(f(N)*g(M)) dove f(N) è la complessità della parte che ha un input del caso peggiore limitato e g(M) è la complessità dell'altra parte.
Ora si può affermare che per la grande M, la parte g(M) domina la complessità complessiva e l'effetto della parte con input limitato può essere trascurato per ulteriori analisi.

score 0 · Answer 3

Dipende da chi sta leggendo questo. L'informatica è solitamente interessata a casi asintotici. Ma nel tuo caso, sembra che tu abbia O (n) dove n è il numero di possibili caratteri diversi, e tu limiti artificialmente n a 128 scegliendo ASCII e richiedi che sia O (1). Bene, vorrei gestire almeno l'intera gamma Unicode (circa un milione di punti di codice) e probabilmente estesi cluster grapheme, che sono illimitati, quindi troverei questo molto insoddisfacente.

In Ingegneria del software, di solito ci occupiamo della velocità con cui viene eseguito nella pratica. Se esegui k operazioni e ogni operazione è un ciclo su 128 caratteri ASCII, ciò avrà un effetto sul runtime e le persone potrebbero considerarti imbrogliare.