私のBig-O理解のテストをブラッシュアップしようとしている(明らかに必要な非常に基本的なBig-Oの理解)私の本でいくつかの練習問題をやっていた。2つのイテレーター変数を持つ配列の2つの半分をカバーする単一whileループのBig-Oh表記
彼らは私に次のコード
public static void swap(int[] a)
{
int i = 0;
int j = a.length-1;
while (i < j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
私が思うに理解するのは簡単を与えました。それは2つのイテレーターのそれぞれが一定量の作業量で配列の半分をカバーしています(これはO(n/2)の両方で計時すると思う)
したがって、O(n/2)+ O (2n/2)= O(n)
これは私の現在の理解であり、問題解決のための私の試みでしたので、許してください。私はbig-oオンラインの多くの例を見つけましたが、イテレータが基本的に同じ時間に配列を増分して修正するところは、これと全く同じです。
これはループが1つあるため、とにかくO(n)だと思うようになっています。
誰でも私のためにこれをクリアすることができますか?
おかげ
FYI:配列の半分を反復する場合でも、たとえば 'sumOddIndexElements()'のように、それはまだO(n)です。 1/2の一定係数がなくなる。より複雑なアルゴリズムの分析を開始する場合、分析の早い段階で正確な数から大きな数に切り替えると便利です。その後、用語を捨てることができるため、中間ステップが簡単になります。 I.サブルーチンがO(n)+ O(log n)の仕事をする場合、残りの分析のためにすぐにO(n)に減らすことができます。 – japreiss
@japreiss申し訳ありませんが、あなたの最後の文章は私をちょっと混乱させてしまいました。私が正しく理解すれば、O(log n)はある時点でO(n)に十分に重要ではなくなり、時間効率に換算する価値がないため、それを落とすでしょうか? – Habitat
big Oの定義によって、用語を追加すると、常に漸近的に最大であるが、すべてを落とすことができます。 'n + log n <2n'だと証明できますが、' 2n'はO(n)です。だから、それは非常に明確な方法では重要ではありません。 – japreiss