とすると、O(nm)をO(n)に減らすことはできますか？2つの変数を持つBig-O表記。 m <= nであれば、O（nm）を減らすことはできますか？
私はないと思うだろう、mはm < nの場合n
に等しくすることができるので、私はmがnより厳密に小さく、従ってnアプローチとして無意味になるためO(nm)がO(n)に低減することができると思うだろう無限
私は上記の仮定で正しいですか？もしそうなら、なぜですか？これを示すもっと正式な方法は何ですか？
mが定数（例：2）以下の定数の場合は、右の値はO(mn) = O(n)です。
しかし、m < nと書いたので、mも無限になりますが、nより遅くなると思います。
この場合、あなたは間違っています。
例としてm = log(n)を考えてください。すべてが明確でなければなりません。
O(mn) = O(n*log(n))
O(n)とは異なります。
O(m+n)の場合は該当しますが、O(mn)の場合は該当しません。
@EricDuminil、私は両方の場合をカバーするために投稿を編集しました。 –
これは素晴らしい説明です。ありがとうございました – Lneuner
単にO(m*n)をO(n)に減らすことはできません。 mに境界条件がない場合。
m < nつまり、mは、0からn-1の間の任意の値になります。
のはmが制限され、それの値がこの場合
O(m*n) can be reduced to O(n)
PS以上C
m <= C
を育てないCAことを言ってみましょう：を考えると、このplain english big o notaion
を読んでください、すべてをあなたは約O(mn)と言うことができるそれは最悪でO(n**2)です。 mが一定で囲まれている場合
は、O(mn)はO(n)
いいえ、M
BlackBear
O（mn） 。 'O（n ** 2）'と書くこともできますが、情報を失うことになります。 'm 'が束縛されていれば' O（n） 'と書くことができます。 –