Help us understand the problem. What is going on with this article?

Pythonで競プロに挑む日誌 vol.21 ~計算量ってナンデスカ~

More than 1 year has passed since last update.

現在の目標

  • 2018年内に茶色になる←イマココ
    • ABC の A, B 問題を全部解く
  • 2018年度内に緑色を取得する
    • ABC の C 問題を全部解く
  • (水色になったら, APG4b で C++ にも手を出す)

今日のおはなし

結論

  • 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) とかになっていないか確認する習慣をつけましょう.

解いた問題

B - Sum AND Subarray

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 文を使うと直列つなぎみたいになって処理時間がどんどん増えてしまうんですね. 考え易いと思って処理を分割するのは良かったのですが, 裏目に出てしまったようです.
しかしながら, 計算量の見積もり方や, 制約条件の具体的な活用法も学べて, 勉強になりました.

むすび

痛い目をみてひとつ賢くなれた.

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away