この質問があります：
f(n) = log(n) (it's log base 2 btw)
問題が f(n) マイクロ秒かかると仮定すると、1 秒で解決できる問題の最大サイズ n は?
f(n) は log(n) なので、問題は log(n) マイクロ秒かかりますよね？1 秒は 100 万マイクロ秒ですよね？だから私はそれを次のように設定しました：
log(n) = 1000000
しかし、それは答えとして 2^1000000 を与え、それは絶対に不快なほど巨大な数です。私は何か間違ったことをしていますか？
それはいいです。O(log(n)) アルゴリズムは非常に高速です。
もちろん、実生活では f(n) は永遠に log(n) ではありません。データセットで作業している場合、メモリが不足し、遅くなるディスクにヒットし始めます。ある時点で、地球上のすべてのディスク容量が不足するでしょう...
あなたの計算は正しいです。
log(n) 時間で実行されるアルゴリズムは、毎回問題のサイズを半分に削減できるアルゴリズムです。例として、二分探索木でアイテムを見つけることが挙げられます。最悪のケースは、探しているアイテムが葉の 1 つにある場合です。
そのため、子供を選ぶたびに、木の半分を切り落とします。開始時には、2^1 000 000 ノードがあります。次の子に進むと、半分の数のノード (2^999 999) があります。100 万回の操作の後、探していたノードを含むリーフに到達するはずです。