c - O(n) のみのネストされた for ループ

Question

ネストされた for ループを含むが order(n) のみの関数を作成するにはどうすればよいですか? 再帰を使用する必要があるかどうかはわかりません。

Answer 1

内側の for ループが可変数のループではなく一定数のループであり、外側のループが可変数のループである場合 (またはその逆)、時間の計算量は O(n*C) であり、ここで C は定数です。これは単に O(n) を意味します (大きな O 表記は成長因子のみに関係するため)。