回答編集履歴
2
加筆
answer
CHANGED
|
@@ -3,7 +3,7 @@
|
|
|
3
3
|
しかし、計算量を減らす工夫はできます。
|
|
4
4
|
まず、入力された数字を~~小さい順~~**大きい順**に並べ替えます。
|
|
5
5
|
そして、最初に集合S = {0}を考えます。
|
|
6
|
-
一番~~小さい~~**大きい**数字が7で、それが2つあるとき、Sに対して、Sの各要素に7を1回足した集合Tと、7を2回足した集合Uを考えます。そして、Sの要素にTとUの要素を追加します。この時点でSは{0,7,14}となります。あとは入力された各異なる数に対して同様に考えます。
|
|
6
|
+
一番~~小さい~~**大きい**数字が7で、それが2つあるとき、Sに対して、Sの各要素に7を1回足した集合Tと、7を2回足した集合Uを考えます。そして、Sの要素にTとUの要素を追加します。**このとき、TにSの要素とUの要素を追加して、Sと置き換えます。**この時点でSは{0,7,14}となります。あとは入力された各異なる数に対して同様に考えます。
|
|
7
7
|
|
|
8
8
|
|
|
9
|
-
4/26追記：数学の理論としては先の通りなのですが、集合の実装として、2分木を用いている場合、小さい順に追加していくと、木の生成が不均一とな
|
|
9
|
+
4/26追記：数学の理論としては先の通りなのですが、集合の実装として、2分木を用いている場合、小さい順に追加していくと、木の生成が不均一となる、という致命的な欠陥に気がつきましたので、該当箇所を修正しました。
|
1
アルゴリズムの修正
answer
CHANGED
|
@@ -1,6 +1,9 @@
|
|
|
1
1
|
結論から言うと、計算量のオーダーを下げるアルゴリズムは存在しません。例えばn個の数字が1,2,4,8,...であれば、その和は0から2^n-1までのすべての数で、単純計算でn*2(n-1)回程度の可算が必要です。
|
|
2
2
|
|
|
3
3
|
しかし、計算量を減らす工夫はできます。
|
|
4
|
-
まず、入力された数字を小さい順に並べ替えます。
|
|
4
|
+
まず、入力された数字を~~小さい順~~**大きい順**に並べ替えます。
|
|
5
5
|
そして、最初に集合S = {0}を考えます。
|
|
6
|
-
一番小さい数字が7で、それが2つあるとき、Sに対して、Sの各要素に7を1回足した集合Tと、7を2回足した集合Uを考えます。そして、Sの要素にTとUの要素を追加します。この時点でSは{0,7,14}となります。あとは入力された各異なる数に対して同様に考えます。
|
|
6
|
+
一番~~小さい~~**大きい**数字が7で、それが2つあるとき、Sに対して、Sの各要素に7を1回足した集合Tと、7を2回足した集合Uを考えます。そして、Sの要素にTとUの要素を追加します。この時点でSは{0,7,14}となります。あとは入力された各異なる数に対して同様に考えます。
|
|
7
|
+
|
|
8
|
+
|
|
9
|
+
4/26追記：数学の理論としては先の通りなのですが、集合の実装として、2分木を用いている場合、小さい順に追加していくと、木の生成が不均一となり、深さが2^nに比例する、という致命的な欠陥に気がつきましたので、該当箇所を修正しました。
|