java - 単純な固定サイズの整数演算のアルゴリズム効率 (Big-Oh に関して) は?

Question

例えば、

public int sumArray()
{
  int[] arr = new int[10];

  int n = arr.length;

  int sum = (n*(n+1))/2;

  return sum;
}

このアルゴリズムの効率は、O(1)、O(n)、またはその他でしょうか?

Answer 1

の個々のステートメントのそれぞれにsumArray一定の時間がかかるため (nここでは定数である の値とは無関係)、関数全体も同様です。

Answer 2

簡単に言えば、私が理解しているように（もちろん、公式のより正確な何かが必要な場合は、グーグルまたはwikiをチェックしてください）、

Big-O は、リストを並べ替えたり、並べ替え済み/並べ替えられていないリスト内の要素を検索したり、基本的にアイテムのサイズに関して反復を必要とする場合のように、特定のアルゴリズムがどれほど効率的であるかを示します。サイズが大きくなり始めると、より効率的なアルゴリズムを使用して大きな改善が見られます。

あなたの場合、反復は含まれていないため、これは定数時間 O(1) であり、n の値が何であるかは実際には問題ではありません。しかし、1 から n へのループを使用してシグマ N 問題を書き直し、各反復として合計を実行すると、O(n) になります。ご覧のとおり、ソリューションはこの特定の問題のループよりも効率的です。O(1) は O(n) よりも優れています。