選択ソートのBig Oは数学的にどのように計算されますか？

Question

誰かが簡単に英語で計算する方法を説明できますか？
私はあなたがn+2+(n-1)+2+...+2+2要素を訪問しなければならないことを知っていますが、どうすれば1/2n^2 + 5/2n - 3?になりますかありがとう！

Answer 1

n + 2 + (n - 1) + 2 + ... + 2 + 2は(n + 2) + (n + 1) + ... + 4に等しい。それはarithmetic progressionであり、その合計は(n + 2 + 4) * (n + 2 - 4 + 1)/2と計算されます。それは(n + 6) * (n - 1)/2に等しく、最後に1/2 * n^2 + 5/2 * n - 3に等しい。

f(n) = O(g(n))は、そのような定数が存在することを意味する。Cf(n) <= C * g(n)は、すべて十分に大きいnに対して存在する。 nが自然数とみなされる場合、1/2 * n^2 + 5/2 * n - 3 = O(n^2)とC = 3/2などがあります。