はじめに
「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の各問題をPythonを用いて解いていくシリーズです。
問題
要は、このグラフでのdiffが最大化される2点を見つけましょうということです。(ただし、価格が減少し続ける場合は一番マイナスの利益=売却損が小さくなる2点を見つける。)
解法
注意点
- 常に価格が減少し続ける場合を考慮して利益の最大値の初期値を設定する必要がある。
- 利益がマイナスの場合を考慮していないと最大値の初期値を0等にしがちだが、そうしてしまうと本当は赤字なのにプラマイ0という答えを返してしまう。
- 今回はRtの範囲が1~109までなので、どんなに大赤字でも1-109が利益の最小値。ということで初期値は1-109と設定した。もしくは、R1 - R0でも良いかも。
- 当たり前だが、買い付け時を表すindexは売却時のindexよりも小さくなければならない。
- 2<=nなので、与えられるリストのサイズに関するエラーは考慮しなくて良い
1. ブルートフォース|計算量O(n2)
素直に全ての地点同士の利益を算出し、その最大値を求めるやり方。大変シンプルでわかりやすいが、実行に時間がかかる。
import time
def return_max(n_list):
start = time.time()
# 想定される価格の最小値 - 最大値
max_diff = 1 - 10 ** 9
for i in range(len(n_list)):
for j in range(1, len(n_list)):
# 買い付け時のindexは売却時のindexよりも小さくなければならない
if i >= j:
continue
diff = n_list[j] - n_list[i]
if diff > max_diff:
max_diff = diff
print("elapsed_time:{0}".format(time.time() - start))
return max_diff
2. 買い付け時価格の最小値を保持しつつ各地点での利益を計算|計算量O(n)
買い付け時価格の最小値をリストの最初の値とし、二番目の値からリストを走査して各地点での利益を算出する方法。リスト走査が一回で済むので計算量がO(n)となり、ブルートフォースでの手法と比較して実行時間を短くできる。
def return_max2(n_list):
start = time.time()
min_n = n_list[0]
# 想定される価格の最小値 - 最大値
max_diff = 1 - 10 ** 9
for i in range(1, len(n_list)):
max_diff = max(max_diff, n_list[i] - min_n)
min_n = min(min_n, n_list[i])
print("elapsed_time:{0}".format(time.time() - start))
return max_diff
このやり方の時、min_nの更新を各地点での利益計算よりも先にしてしまうと、価格が減少し続ける場合に同じ地点同士で利益計算してしまうので、必ずmax_diffの計算後に更新する。
テストと実行速度測定
テストケース1.価格が上下する場合
以下を実行。お題の1~109の間でランダムに１万個の整数を生成し、アルゴリズムを実行してみた。
n_list = [random.randint(1,10**9) for i in range(10000)]
print("answer", return_max(n_list))
print("answer", return_max2(n_list))
実行結果
実行速度の差が圧倒的。一応計算してみると、解法2は1の0.0000000071倍の時間で計算が終了している。
テストケース2. 価格が増加し続ける場合
以下を実行。同様の手法でリストを生成し、sort()で昇順に並べ替えた。
n_list = [random.randint(1,10**9) for i in range(10000)]
n_list.sort()
print("answer", return_max(n_list))
print("answer", return_max2(n_list))
実行結果
やはり解法2が圧倒的に早い。
テストケース3. 価格が減少し続ける場合
sort(reverse=True)で降順に並べ替えて実行。
n_list = [random.randint(1,10**9) for i in range(10000)]
n_list.sort(reverse=True)
print("answer", return_max(n_list))
print("answer", return_max2(n_list))
実行結果
やはり解法2が圧倒的に早い。
まとめ
O(n2)とO(n)を比較すると、O(n)の解法が圧倒的に早い。早すぎる。
感想
実際にアルゴリズムを動かすとO(n2)とO(n)の実行速度の違いがあまりにも顕著で、正直なところ驚いた(笑)。理論的な実行速度の違いのカーブを見せられてもあまり実感が沸かないが、実際に実行してみると雲泥の差があることが身に沁みてわかった。
