Mengapa fungsi ini dapat dihitung dalam waktu

Buku teks saya mengatakan: "Kami mendefinisikan fungsi$f\colon \mathbb{N}\to\mathbb{N}$ sebagai berikut: $f(1)=2$ dan $f(i+1)=2^{f(i)^{1.2}}$ . Perhatikan bahwa diberikan $n$ , kita dapat dengan mudah menemukan di $O(n^{1.5})$ waktu jumlah $i$ sehingga $n$ terjepit di antara $f(i)$ dan $f(i+1)$ ."

Bagaimana saya dapat meyakinkan diri sendiri bahwa kita dapat dengan mudah menemukan dalam waktu O ( n 1,5 ) ? Karena f didefinisikan secara berulang, saya pikir kita harus menghitung f ( 1 ) , f ( 2 ) , f ( 3 ) ... f ( j ) hingga f ( j ) ≥ n . Untuk mengetahui waktu yang dibutuhkan perhitungan ini, saya pikir kita harus menemukan batas atas yang cocok untuk saya bergantung pada $i$$O(n^{1.5})$$f$$f(1),f(2),f(3)\dots f(j)$$f(j)\geq n$$i$$n$dan kita harus menemukan batas atas pada waktu eksekusi fungsi . Pada akhirnya, kami harap dapat menunjukkan proposisi yang dikutip. Sayangnya, saya tidak melihat satu hal maupun yang lain.$x\to2^{x^{1.2}}$

Saya lupa menyebutkan: Harap dicatat bahwa kita berada dalam konteks nondeterministik. Jadi diklaim dapat dihitung dalam O ( n 1,5 ) oleh mesin Turing nondeterministic.$f$$O(n^{1.5})$

Seperti beberapa orang sudah membaca pertanyaan ini, dengan beberapa dari mereka menemukan itu berguna dan menarik juga, tetapi tidak ada yang menjawab sejauh ini, saya ingin memberikan beberapa informasi lebih lanjut tentang konteksnya: Klaim yang dikutip merupakan bagian integral dari bukti teorema hierarki waktu nondeterministik. Buktinya (dengan klaim) dapat ditemukan misalnya dalam buku oleh Arora dan Barak , tetapi saya telah menemukan beberapa sumber daya lain di Web juga yang menyajikan bukti yang sama. Masing-masing dari mereka menyebut klaim itu mudah atau sepele dan tidak menjelaskan bagaimana menemukan dalam waktu O ( n 1,5 ) . Jadi semua sumber daya ini hanya disalin dari Arora dan Barak atau klaim sebenarnya tidak terlalu sulit.$i$$O(n^{1.5})$

Dilambangkan oleh panjang angka x , yaitu ⌊ log 2 x ⌋ + 1 (untuk x > 0 ). Menghitung 2 x membutuhkan waktu O ( x ) dalam model RAM, sehingga menghitung f ( i + 1 ) dari f ( i ) membutuhkan waktu O ( f ( i ) 1.2 ) = O ( |$|x|$$x$$\lfloor \log_2 x \rfloor + 1$$x > 0$$2^x$$O(x)$$f(i+1)$$f(i)$ . Karena f ( i ) tumbuh lebih cepat daripada geometris, waktu keseluruhan untuk menghitung f ( i + 1 ) adalah O ( | f ( i + 1 ) | ) . Seperti yang Anda tunjukkan, Anda perlu melakukannya sampai f ( i + 1 ) ≥ n , yang berarti f ( i ) < n . Oleh karena itu total waktu berjalan adalah$O(f(i)^{1.2}) = O(|f(i+1)|)$$f(i)$$f(i+1)$$O(|f(i+1)|)$$f(i+1) \geq n$$f(i) < n$ .$O(|f(i+1)|) = O(f(i)^{1.2}) = O(n^{1.2})$

Dalam model mesin Turing dengan satu pita, menghitung membutuhkan waktu O ( x log x ) , sehingga total waktu berjalan adalah O ( n 1,2 log n ) = O ( n 1,5 ) . Algoritma untuk menghitung 2 x menggantikan [ x ] dengan 1 [ [ x ] ] (di sini [ x ] adalah representasi biner dari x , dan [ $2^x$$O(x\log x)$$O(n^{1.2} \log n) = O(n^{1.5})$$2^x$$[x]$$1[[x]]$$[x]$$x$ adalah representasi biner menggunakan digit berbeda 0 ′ , 1 ′ ), dan kemudian berulang kali menjalankan transformasi [ [ x ] ] ⟶ 0 [ [ x - 1 ] ] , yang membutuhkan waktu O ( | x | ) = O ( log x ) .$[[x]]$$0',1'$$[[x]] \longrightarrow 0[[x-1]]$$O(|x|) = O(\log x)$