Apakah pernyataan dari algoritma dasar Knuth ini masih berlaku hari ini? [Tutup]

10

Dalam arti, 10! (sepuluh faktorial) merupakan garis pemisah perkiraan antara hal-hal yang praktis untuk dihitung dan hal-hal yang tidak.

Ini dari buku TAOCP Fundamental Algorithms book (1973). Apakah ini masih pernyataan yang valid atau memiliki daya komputasi yang membuatnya usang?

computer-science taocp Bon Ami
sumber
Bagi saya tidak jelas dalam arti apa itu benar - 10! hanya beberapa juta. Terlalu besar untuk pemahaman langsung, tetapi tidak terlalu sulit untuk dihitung, bahkan dengan pena dan kertas.
hobbs
11
@ hobbs ini tidak berbicara tentang menghitung nilai 10!, ini berbicara tentang melakukan perhitungan pada sekitar 10! hal-hal . Yaitu, jika metode Anda membutuhkan lebih dari sekitar 10! <unit kerja>, saatnya mencari metode baru.
AakashM

Jawaban:

21

Itu masih masuk akal.

10! = 3,628,880. Setiap langkah setelah itu naik SETIDAKNYA urutan besarnya.

(fact 10)
3628800

(fact 11)
39916800 -- about 40 million

(fact 12)
479001600 -- almost 500 million

(fact 13.0)
6227020800.0 -- over 6 billion

Segera, Anda sedang berbicara tentang angka pengeluaran Kongres.

John R. Strohm
sumber
15

Untungnya, profesor yang baik masih bersama kita dan cara terbaik untuk memastikan jawaban yang pasti adalah dengan menulis kepadanya dan menanyakan pendapatnya.

Yang mengatakan, saya tidak berpikir angka absolut penting seperti fungsi yang mewakili faktorial. Terlepas dari apakah Knuth menyadarinya pada saat itu, model yang ia buat dengan pernyataan itu bekerja sangat baik untuk melihat ke belakang pada apa yang praktis untuk dihitung pada dekade-dekade sebelumnya dan maju melalui yang mengikuti.

Pada tahun 1973, kapasitas kami untuk menghasilkan, menyimpan, mentransfer, dan memproses data cukup terbatas untuk menghasilkan 10! angka "jauh" untuk masuk akal. Saya ragu Knuth (atau orang lain, dalam hal ini) akan dapat memprediksi peningkatan eksponensial di hampir semua yang kami nikmati sejak saat itu, tetapi faktorial telah sesuai dengan angka aktual dengan baik.

Saya telah melihat ini secara langsung: Satu dekade yang lalu, saya bekerja pada sebuah proyek di mana kami mengembangkan cara untuk menyimpan dan memproses sekitar 50 juta catatan sementara pada saat yang sama merenungkan bagaimana kami akan melakukan pemesanan lebih banyak. Satu dekade kemudian, saya melakukan proyek serupa. Angka-angka target saya telah bergeser, semuanya dengan faktorial:

                      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

Kelompok-kelompok yang melakukan kedua proyek ini lebih banyak membicarakan angka-angka bulat daripada angka-angka itu, tetapi faktorialnya tidak terlalu jauh. Googles dan Facebook di dunia memiliki sumber daya untuk melakukan hal-hal yang hanya diimpikan oleh proyek saya saat ini, tetapi dari tempat saya duduk, 13!dalam satu dekade atau kurang tampaknya tidak terlalu jauh dari jangkauan.

Saya tidak berpikir tentang data dalam jumlah besar pada tahun 1992, tetapi menurut saya mungkin saya telah melihat semua yang kurang satu faktorial.

Blrfl
sumber