Notazione Theta in tempo costante. Perché usiamo l'1?

Queste notazioni hanno lo scopo di denotare la crescita asintotica. Le costanti non crescono e quindi è abbastanza uguale quale costante scegli. Tuttavia, c'è una convenzione che scegli 1 per indicare nessuna crescita.

Suppongo che ciò sia dovuto al fatto che vuoi semplificare i termini matematici in questione. Quando hai un fattore costante, basta dividerlo e tutto ciò che ne rimane è 1. Questo facilita il confronto.

Esempio:

O (34 * n ^ 2) = O (1 * n ^ 2) = O (n ^ 2)

e

O (2567.2343 * n ^ 2/5) = O (n ^ 2)

Vedi cosa intendo? Poiché questi termini matematici diventano sempre più complicati, non vuoi avere costanti rumorose quando non sono rilevanti per le informazioni che ti interessano. Perché dovrei scrivere O (2342.4534675767) quando può essere più facile espresso con O (1), che comunica i fatti del caso in modo inequivocabile.

Inoltre, l' articolo di wikipedia sulla complessità temporale implica anche che si tratta di una convenzione:

An algorithm is said to be constant time (also written as O(1) time) ...

Questo è tutto molto ondulato a mano, ma c'è una ragione matematica per cui non usiamo Theta (c) e invece usiamo Theta (1). Userò la notazione Big O per mostrarlo.

Ha a che fare con una proprietà della notazione Big Theta (così come Big O e Big Omega). Se hai una funzione con tasso di crescita O(g(x)) e un'altra con tasso di crescita O(c * g(x)) dove c è una certa costante, diresti che hanno lo stesso tasso di crescita. Questo è O(c * g(x)) = O(g(x))

Possiamo dire questo perché la definizione di notazione Big O ( f(x) = O(g(x)) ) significa che abbiamo una funzione f(x) e funzione g(x) tali che |f(x)| <= k * |g(x)| per alcuni costanti k e valori abbastanza grandi di% codice%. Quando si moltiplica per la costante x , avremmo quindi:

c dove O(c * g(x)) => k * |c * g(x)| = k * |c| * |g(x)| <= k' * g(x)

Tieni presente che k' = k * |c| per alcuni |k' * g(x)| <= k'' g(x) costanti e valori abbastanza grandi di k'' , il che significa che x cresce ad un tasso di k' * g(x) e quindi O(g(x))

Quando O(c * g(x)) = O(g(x)) , abbiamo g(x) = 1 crescita, dicendo O(1) crescita per un valore di O(c) non ci dice nulla perché la costante è già calcolata nella definizione di notazione Big O. c semplificato

Beh, ovviamente potresti scrivere Theta (c) (o O (c)) ma perché questo differisce da Theta (n)? n è solo una variabile che denota la dimensione dell'input. Potresti scrivere "La funzione è Theta (c) dove c è una costante". L'importante addendum è ... dove c è una costante . Devi dichiarare esplicitamente che un identificatore non è una variabile.

Considera la teoria dei grafi in cui i limiti di un algoritmo sono spesso descritti come una funzione di | V | e | E |, o il conteggio dei nodi e dei fronti, rispettivamente. Quindi potrebbe essere prudente dichiarare "La funzione è Theta (| V | * | E | ^ 2)".

Theta (1) tuttavia è sempre una costante - assumendo normali pratiche matematiche.

La notazione Theta riguarda la crescita in funzione di alcune variabili, tipicamente n. Se fosse necessario chiarire quale variabile è intesa, il modo di scriverlo sarebbe Theta (n ^ 0). Da lì è un semplice passaggio per applicare l'identità n ^ 0 = 1 (per n! = 0).

O ( c ) in particolare significa che la classe associata di algoritmi cresce linearmente con c , dove c è la dimensione di un input all'algoritmo o un parametro all'algoritmo . Non è lo stesso c che viene usato per spiegare la notazione O, perché c è rilevante solo per la spiegazione, non per l'uso. O ( c ) contiene un c diverso che deve provenire dal contesto di input dell'algoritmo.