1. ホーム
  2. algorithm

[解決済み] どちらが大きいですか?O(log*n)とO(loglog n)

2022-03-04 01:27:34

質問

時間的な複雑さとの間で混乱がある O(log*n) O(loglog n) というのがあって、どっちが大きいか知りたかった。

何か参考になることはありますか?

解決方法は?

O(log* n) よりも高速です。 O(log log n) は、ある閾値を超えると

log* n を何回やればいいのかが書かれています。 log*(log n) になる前に、1+1 になります。 log* を実行したときの残量の log(log n) まで log N < 1

つまり、この値の計算は再帰的に行われるのです。

について n = 2^512
log*n を4つ贈呈します。
ここで log log n = 5.17