for (int i = 1; i < a; i++){
for(int j = 1; j < b; j = j + a){
Function() <-- O(1)
}
}
、外側ループは「a'times（O（A））を、及び 内側ループが実行される 『実行されるB /』回（ O（b/a））である。可変インクリメントループ、この場合、時間の複雑
次に、合計時間複雑度はO（a * b/a）= O（b）ですか？
私はこの解釈が正しいかどうかではないよ...
まあO(a * b/a) = O(b)身元がすぐそこにあります右のため、明らかである：O(b*a/a) = O(b*1) = O(b)。
しかし、時間の複雑さがO(a*b*1)であると思われます（ループするとオーバーヘッドが発生しないものとします）。計算の労力は、個々のループサイズごとに直線的に増加します。それがO(a*b)の理由です。
内側のループにタイプミスがあります。もう一度確認してください – NoSleep
Armenが正しいです、答えはO（ab）です。私たちは、これらの手順で答えを得ることができます。
O-Bを-a（（-1）（B-1）（1））
= O（AB-AB + 1）、 +1は無視できます。
= O（AB）
内側のループを編集しました。再度確認してください – NoSleep
私は、元の複雑さがO(a) * O(b/a)
である必要があり、それは私の考えは
で、良い質問だと思う。しかし、あなたが結論に飛び込む前に、あなたが判断しなければなりません例：
もしb <= a、その後、O(b/a) = O(1)、そうO(a) * O(b/a) = O(a)
a回を渡すので、
b > a場合、O(b/a) = O(b/a)、そう= O(b)
O(a) * O(b/a)だからこれらのケースを組み合わせた、私はそれがO(max(a,b))
O(b)だと思いますが正しくありません少なくともO(a)になります（ご存じのように、bはaよりもはるかに小さいかもしれません）。答えは、bだけではなく、aとbの両方に依存する必要があります。慎重にカウント
は、あなたは、内側のループをceil((b-1)/a)回を渡すので、複雑さが
O(a*ceil((b-1)/a))
である。しかし、このように
ceil((b-1)/a) <= (b-1)/a + 1
a*ceil((b-1)/a) <= a*((b-1)/a + 1) = b - 1 + a = a + b - 1
1は漸近的に無視できる程度です、したがって、複雑さはO(a+b)です。
O(a+b) = O(max(a,b))これは@sholeの回答に同意します。
[Big O、それはどのように計算/近似しますか？]（http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it） –
内部ループは 'b/a'回実行されますか？ループ自体は 'b'回繰り返され（' Function（） '）、それ自体（' for（int j = 1 ...）{...} '）は' a'回繰り返されます。 – Paul
@Paul内部のループを編集しました。再度確認してください。 – NoSleep