複雑さ（N *（N-1）/ 2）

Question

：(n(n-1))/2

あなたはこの方程式を表現するためのアルゴリズムを記述した場合、どのような複雑になりますアルゴリズム？

Answer 1

(n*(n-1))/2は、(1 + 2 + ... + (n-1))と表すことができます。この拡張された式を使用して合計を求めると、O(n)時間の複雑さとO(1)の空間の複雑さがあります。

(n*(n-1))/2をsum-expressionに展開しないと、(n*(n-1))/2を実行するには時間の複雑さがO(1)になります。

なぜO(n)拡張（合計）式ですか？

(n-1)要素を1つずつ考慮して追加を行う予定です。 したがってO(n)はO(n-1)と同じと見なされます。

Answer 2

(n*(n-1))/2の時間複雑度は、O(n^2)になります。

この式1+2+3+4+...n-1は、O(n)アルゴリズムで評価できます。そして、「結果の式」の時間の複雑さは常に同じ（または線形）である必要はありません。 Big O表記は、そういうものには適用できません。

関数が(n*(n-1))/2と表される場合、その成長率は線形ではありません。そして、ランダウの記号は、関数の成長率についてお話しますので、(n*(n-1))/2の時間計算量は、nの値が大きいほどため(n*(n-1))を計算しながら、あなたはそれぞれすべての桁を格納する必要があり、具体的にO(n^2)

です配列の中にある数を除いて、それを乗算します。これは、O(N^2)時間複雑さを要し、Nは桁数です。