In a sense, 10! (ten factorial) represents an approximate dividing line between things which are practical to compute and things which are not.
Questo è tratto dal libro di Knuth TAOCP Fundamental Algorithms (1973). Questa è ancora una dichiarazione valida o la potenza di calcolo lo ha reso obsoleto?
È ancora ragionevole.
10! = 3,628,880. Ogni passo successivo aumenta di almeno un ordine di grandezza.
(fact 10)
3628800
(fact 11)
39916800 -- about 40 million
(fact 12)
479001600 -- almost 500 million
(fact 13.0)
6227020800.0 -- over 6 billion
Molto presto, stai parlando dei numeri di spesa del Congresso.
Il buon professore è, fortunatamente, ancora con noi e il modo migliore per accertare una risposta definitiva è scrivergli e chiedere la sua opinione.
Detto questo, non penso che il numero assoluto sia importante quanto la funzione che i fattoriali rappresentano. Indipendentemente dal fatto che Knuth se ne sia reso conto al momento, il modello che ha stabilito con questa affermazione funziona molto bene per guardare indietro a ciò che era pratico da calcolare nei decenni precedenti e in avanti attraverso quelli che seguirono.
Nel 1973, la nostra capacità di generare, archiviare, trasferire ed elaborare i dati era abbastanza limitata da fare 10! una cifra ragionevole "lontano" da fotografare. Dubito che Knuth (o chiunque altro, del resto) sarebbe stato in grado di prevedere i miglioramenti esponenziali in quasi tutto ciò che ci è piaciuto da allora, ma i fattoriali hanno adattato bene i numeri reali.
L'ho visto in prima persona: dieci anni fa, ho lavorato a un progetto in cui stavamo sviluppando modi per archiviare ed elaborare circa 50 milioni di record, mentre allo stesso tempo riflettevamo su come avremmo fatto un ordine di grandezza in più. Un decennio dopo, sto facendo un progetto simile. Le mie figure target sono cambiate, tutte in modo fattoriale:
2002 2012
Small Test ....... 9! / 362K ... 10! / 3.6M
Large Test ....... 10! / 3.6M ... 11! / 40M
Capacity Goal .... 11! / 40M ... 12! / 479M
Capacity Dream ... 12! / 479M ... 13! / 6.3B
I gruppi che eseguono entrambi i progetti hanno messo insieme cifre molto più arrotondate di quelle, ma i fattoriali non sono molto lontani. I Googles e Facebook del mondo hanno le risorse per fare il genere di cose che il mio progetto attuale sogna, ma da dove mi siedo, 13! in un decennio o meno non sembra poi così lontano.
Non pensavo a grandi quantità di dati nel 1992, ma il senno di poi dice che probabilmente avrei guardato a tutto meno di un factorial.
Leggi altre domande sui tag computer-science taocp