実行時間（＾～＾）

「　実行時間分かんねー」

「　お父んは　体験しないと分かんないからな」

「　１００億年ぐらい待機するといいわよ」

📖　アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書 Kindle版

「　👆　この本の練習問題を　練習しようぜ？」

「　プログラムの命令数を　ｎ　としよう」

「　プログラムを　１命令　実行するのにかかる時間を　１μｓ（マイクロ秒）　としようぜ？」

「　マイクロ秒　って何？」

「　１秒は　１０００ミリ秒。
１ミリ秒は　１０００マイクロ秒だぜ」

「　じゃあ　１秒は　１，０００，０００（百万）マイクロ秒　だな」

「　コンピューターって　１秒間に　１００万命令も　計算できるもんなの？」

「　1 MIPS （Million Instructions Per Second） というやつだな」

「　じゃあ、時間を　t　で与えるから、　何 n まで処理できるか計算しろだぜ」

「　その数学みたいな言い回し、分かんね」

t = 1秒

「　だから　１，０００，０００（百万）命令だぜ」

「　それ　ｎ　な」

「　ｎ　以外に何があるんだぜ？」

t = 1秒。lg n

「　lg n　って何？」

「　底（てい）が　ｅ（ネイピア数）のときの　対数だぜ」

「　どうやって　計算すんだぜ？」

「　lg 1,000,000　かなあ。 Wolfram alpha で計算すると　6」

「　6 命令しか実行できないなんてわけ　なくない？」

「　1 の対数は 0 だしな」

「　1秒ってことは、1マイクロ秒の　100万倍の命令を実行できるってことじゃないの？」

「　それを　lg n」

「　👆　それ、処理時間みたいよ？」

「　じゃあ　n　は　100万固定でいいんじゃないか？　定数な」

「　１００万命令と、　処理速度の違うマシンスペックと、　処理時間が　問題として与えられたわけかだぜ」

「　うーん、こう？　あれっ、　１００万命令って　どこから来たんだぜ？」

「　ｎ　を求めんじゃないの？」

「　👆　１秒あって　マシンスペックが　ｎマイクロ秒なら、　処理件数は　1,000,000　だろ。ここは埋まる」

「　その行　埋めてしまおうぜ？」

「　👆　こんな表埋めてても　何も面白くないんだが」

「　👆　なんか数が　逆な気がするんだよな」

「　👆　こういうわけでもないのか」

「　n って何なんだぜ？」

「　1,000,000 だろ」

「　だから　ｎ　を求めんじゃないの？」

「　ｎ　が　1,000,000 だろ」

「　そんなことが　あるのだろうか？」

「　👆　数学チャンネルによると、上式の　ｎ　を求めろって　ことらしいわよ」

「　じゃあ　お父んは　何もせず　数学チャンネルに問題を解いてもらおうぜ？」

「　多分　その答えは　6　なんだろうけど」

「　↑　いや、 434294.4……だぜ。　お父んは　黙ってろだぜ」

「　↑　うーむ、こんな雰囲気かなあ」

「　↑　もう疲れた……」

「　↑　これでいいだろ」

「　数学でなくなってるぜ」

「　数学できないなら　プログラムでタイムを計りましょう！」

import math

# log2 は 終わらない（＾～＾）
# ("log2 n", lambda n:math.log2(n)),
# sqrt も終わらない（＾～＾）
# ("√n", lambda n:math.sqrt(n)),
test_cases = [
    ("n", lambda n: n),
    ("n log2 n", lambda n:n*math.log2(n)),
    ("n^2", lambda n:n**2),
    ("n^3", lambda n:n**3),
    ("2^n", lambda n:2**n),
    ("n!", lambda n:math.factorial(n))]

# 制限時間（単位：秒）
time_required_list = [1.0]

for test_case in test_cases:
    for t in time_required_list:
        # 処理件数
        n = 1  # 0 開始は無理（＾～＾）

        while True:
            if t < (test_case[1](n))/1_000_000:
                break

            n += 1

        print(
            f"{t} 秒で 1,000,000個処理できるマシンの性能が {test_case[0]:>8} になると、{t} 秒では {n-1:>7}個 処理するので精一杯だぜ（＾ｑ＾）")

1.0 秒で 1,000,000個処理できるマシンの性能が        n になると、1.0 秒では 1000000個 処理するので精一杯だぜ（＾ｑ＾）
1.0 秒で 1,000,000個処理できるマシンの性能が n log2 n になると、1.0 秒では   62746個 処理するので精一杯だぜ（＾ｑ＾）
1.0 秒で 1,000,000個処理できるマシンの性能が      n^2 になると、1.0 秒では    1000個 処理するので精一杯だぜ（＾ｑ＾）
1.0 秒で 1,000,000個処理できるマシンの性能が      n^3 になると、1.0 秒では     100個 処理するので精一杯だぜ（＾ｑ＾）
1.0 秒で 1,000,000個処理できるマシンの性能が      2^n になると、1.0 秒では      19個 処理するので精一杯だぜ（＾ｑ＾）
1.0 秒で 1,000,000個処理できるマシンの性能が       n! になると、1.0 秒では       9個 処理するので精一杯だぜ（＾ｑ＾）