void compute(int n) {
int h = n;
while (h > 1) {
for (int i = 0; i < n; i++) {
// do some operation
}
h = h / 2;
}
}
このnの関数の複雑さ（Big O）を教えてもらえますか？
これは実際、私と私の友人の間の議論です。私の立場：複雑さはO（n * log（n））友人の立場：log（n）
ご回答ありがとうございます。
すべての実行でhが半分になり、n回の演算が実行されるため、O（n * log n）になります。
これが宿題である場合（そしてそれは少し似ているように聞こえます）、最初に自分で試してみるべきです。
基本的に、完全性を得るには、関数の構造、つまりループ、ネストループなどを調べ、それらが実行される時間、依存する入力などを決定します。
この場合、入力は1つだけです。n。ローカル変数hはnと同じ値で始まるため、複雑さに関しては基本的に同じですが、使用方法を追跡する必要があります。
ここには基本的に2つのネストされたループがあります。1つはnまで実行され、もう1つはその周りに実行され、実行されるたびにhが半分になります。したがって、この関数はO（n・log 2 n）にあります。
いくつかの操作：
O(x)
forループ：n> = hであり、「何らかの操作」中にhが変更されないと仮定した場合：
O(n*x)
外側のwhileループ：
O(log(n)*n*x)
O（n.sqrt（n））のようです
外側のループは明らかにnであり、内側のループはsqrt（n）です。
編集：反復回数はxであり、2 ^ x = nであるため、内部ループは正しくlog（n）です。
明らかにn*log(h)です。