2

実行時間は O(n) である必要があります。これは私が思いついたものです。正しいですか? ありがとう

for (i = 1 ; i < A[n]; i++)
  A[i] = 0

B[i] = 0;
for i in A[1..n]
  B[i] = B[i] + A[i]
4

1 に答える 1

0

はい、これは正しいです。あなたのソリューションは、動的計画法の最も自明なケースです。これは、小さなサブ問題のソリューションから構築できるソリューションのアルゴリズムを大幅に高速化する手法です。

目の前の問題はまさにこの特性を持っています: の解が与えられた場合に の解をB[n]構築することができ、それが の実行時間でアルゴリズムが行ったことです。O(1)B[n-1]O(N)

そのような解決策は実際には非常に役立ちます: 私はかつてあなたのようなアルゴリズムを使用して、プログラムの起動コードの一部を数分から数秒に高速化しました (ベクトルを追加していたため、 から になりましO(3)たO(2))。

于 2012-07-21T11:16:59.497 に答える