Tempo complessità di questo frammento di codice

Question

Recentemente, mi sono imbattuto in un frammento di codice:

int i = 1; 
while (N > 1) 
{ 
     N = N/i; 
     i = i + 1; 
} 

sull'osservazione, era evidente che i aumenta linearmente, e i divide N in ogni fase di esecuzione del ciclo, quindi abbiamo potuto affermare che N si riduce in funzione di una funzione inversa di un fattoriale .

come potremmo rappresentare questo nel theta notazione, come inversa fattoriale non è definita per ogni numero naturale N? Dovremmo essere sufficienti usando i limiti superiori e inferiori approssimativi di questa funzione?

Answer 1

Beh, non ne sono sicuro, ma ci provo. Il fattoriale è, in sostanza, un gamma function. E la funzione gamma è definita non solo per i numeri naturali, ma anche per i numeri reali. Quindi, c'è, in teoria, una funzione gamma inversa, che è definita per casi, dove factorial è indefinito (ad esempio, non conosciamo il fattoriale inverso di 5, ma sappiamo che la funzione gamma inversa di 5 sarà essere qualcosa intorno a due punti, qualcosa). Secondo MathOverflow, non esiste una formula precisa per la funzione gamma inversa, ma esistono soluzioni approssimative.

Supponiamo che esista la funzione gamma inversa, e scriviamola come InvGamma(N). Si tratta di un numero reale (potrebbe essere R +, ma non sono sicuro, non è importante ora, dal momento che il nostro N è sempre positivo, al di là di N == 0 caso, che mi ignorano per ora).

Quindi possiamo usarlo allo stesso modo in cui usiamo altre funzioni che restituiscono un numero reale, quando ci occupiamo di complessità: possiamo floor (arrotondarlo per difetto). Proprio come facciamo con la complessità log. Scrivevo usando parentesi quadre (ad esempio log(15) = 1.18, [log(15)] = 1).

Poi la complessità del frammento dovrebbe essere O([InvGamma(N)]), credo.

UPDATE: (ispirato @ risposta 6502): notare che se N è un numero intero (non è menzionato nel frammento di codice), allora ci sarà un arrotondamento ad ogni passo, che altera complessità in un modo complicato . La soluzione di cui sopra funziona per veri N s.

Answer 2

L'estensione "naturale" di fattoriale a tutto il piano complesso tranne gli interi negativi è denominata "gamma function" e su tutti i numeri interi non negativi gamma(n) = (n-1)!.

Si potrebbe quindi invertire una porzione di gamma per calcolare il numero approssimativo di iterazioni necessarie ma non sono sicuro che questo porterebbe ad un esatto calcolo del numero di iterazioni come in quel codice non è un'operazione di arrotondamento a ogni passo.