現在の目標
今日のおはなし
結論
- O(f(x)) は, 「入力 x の増加に対して, 実行時間がどの程度増加するか表す指標」である.
- 一般的には, 「性能が良い ←O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(n^3) ＜O(k^n) <O(n!)→ 性能が悪い」とされている.
- 自分のコードを眺めてみて, O(n^3) とかになっていないか確認する習慣をつけましょう.
解いた問題
TLE 祭りになった解答
WA が出てなかったので計算はできてると思うのですが, ほとんど TLE になってしまいました.
TLE.py
# coding: utf-8
import itertools
N, K = map(int, input().split())
N1 = N*(N+1)//2
lst_a = list(map(int, input().split()))
# beauty を網羅
def beauty(n, lst):
lst_beauty = list([sum(lst[i:j]) for i in range(n) for j in range(i+1, n+1)])
return lst_beauty
lst_beauty = beauty(N, lst_a)
# AND 演算すべき beauty の組み合わせをピックアップ
def pickup_beauty(k, lst):
lst_c = list(itertools.combinations(lst, k))
return lst_c
lst_pickup = pickup_beauty(K, lst_beauty)
# ピックアップした組合せのうち、最大の値を求める
def and_max(lst):
val=0
for p in lst:
tmp = p[0]
for i in p:
tmp &= i
if tmp > val:
val = tmp
return val
print(and_max(lst_pickup))
計算量が多くて TLE が発生したことはすぐにわかったのですが, どのように計算量の見当をつければよいかわかりませんでした.
教プロ界隈でよく出てくる, 「計算量O(f(x))」なるものを理解できていなかったので, Twitter で教えてもらったり, 調べてみました.
計算量とは何ぞや
下記を一通り読めば, 計算量についておおまかに理解できると思います.
どの解説にもありますが, 「入力サイズの増加に伴い, 処理がどのような関数に従って増えるかを表す指標」を使って計算量の見当をつけられるようです.
私は「計算量」という言葉を聴いたときに, 扱う対象が処理時間なのか処理回数なのか混乱しました. これらは本質的には同じ（回数増えれば時間も増える）なので, あまり気にしなくてよいと思います. 初心者はまず, 「入れ子構造の for 文が増えるほど, 指数関数的に処理に時間がかかる」というのがイメージしやすいかもしれません.
（合ってるか知らんけど, ）今回の解答で計算量を見繕うと, O(N * NlogN * N(N+1)/2) → O(N^4 logN) とかになって, だいぶアカンかったことがわかりました.
自分で定義した関数の各々で for 文を使うと直列つなぎみたいになって処理時間がどんどん増えてしまうんですね. 考え易いと思って処理を分割するのは良かったのですが, 裏目に出てしまったようです.
しかしながら, 計算量の見積もり方や, 制約条件の具体的な活用法も学べて, 勉強になりました.
むすび
痛い目をみてひとつ賢くなれた.