合計数列 (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)

この記事では、シーケンス (n^2 - 1^2) 2(n^2 - 2^2) の合計を計算するさまざまな方法を見ていきます。 n(n ^2 - n^2)。最初の方法では、1 から n の範囲内の各 i のシーケンスの合計を 1 つずつ計算し、それを最終的な合計に加算します。

2 番目のアプローチでは、特定の系列の合計を計算する数式を導出します。これにより、プログラムの時間計算量が O(n) から O(1) に軽減されます。

問題文 - 数値「n」が与えられ、私たちのタスクは、指定されたシーケンス (n^2 - 1^2) 2(n^2 - 2^2) の合計を計算することです。 ) …. n (n^2 - n^2)。

＃＃＃例＃＃＃

入力

- 数値 = 5

出力

- n = 5の場合、系列(n^2 - 1^2) 2(n^2 - 2^2) …. n(n^2 - n^2)合計は150です。

入力

- 数値 = 3

出力

- n = 3の場合、級数 (n^2 - 1^2) 2 (n^2 - 2^2) ....n (n^2 - n^2) ) 合計は 18 です。 方法 1

これは、シーケンスの合計問題を解決するための最も単純な強引な方法です。

このシーケンスを注意深く分析した後、次の結論が得られます: 任意の数 n について、

Sum = ∑ i*(n^2 - i^2) (i = 1 から i = n まで)。

したがって、総当り方式の場合、上記の式をループ内で使用し、i を 1 から n まで指定して、必要な合計を生成できます。

＃＃＃例＃＃＃

このメソッドのコードは次のとおりです:

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃複雑＃＃＃

時間計算量 - 1 から n までの数値をループで繰り返すため、O(n)。

空間複雑度 - 外部空間を使用しないため、このメソッドの空間複雑度は O(1) です。

方法 2

このアプローチでは、必要なシーケンスの合計を直接取得する式を導き出すため、反復は必要なく、このアプローチは一定の時間計算量で指定された問題を解決します。

前に述べたように、

として与えられるシリーズの一般バージョンを取得します。 リーリー

同じシリーズは次のように書くことができます:

リーリー

1 から n までのすべての数値の合計を計算する式と、1 から n までのすべての数値の 3 乗の合計を計算する式は、それぞれすでに知っています。

1 から n までのすべての数値の合計

リーリー

ここで、n は指定された数値です。

次に、1 から n までのすべての数値の 3 乗和を求めます。

リーリー

したがって、指定されたシリーズは -

と書くことができます。 リーリー

Sum はさらに -

に簡略化できます。 リーリー

したがって、任意の n に対して Sum = (n^4)/4 - (n^2)/4 を計算するだけで、目的のシーケンスの合計を取得できます。

＃＃＃例＃＃＃

このメソッドのコードは次のとおりです:

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃複雑＃＃＃

時間計算量 - O(1)。導出した式を使用して必要な合計を計算するだけなので。

空間複雑度 - 外部空間を使用しないため、このメソッドの空間複雑度は O(1) です。

結論 - この記事では、必要な系列の合計を計算する 2 つの方法について説明し、2 番目の方法では時間計算量を定数に削減しました。

以上が合計数列 (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。