質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.76%

  • アルゴリズム

    381questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Pythonコードの計算量オーダーの添削をお願いします

解決済

回答 2

投稿

  • 評価
  • クリップ 1
  • VIEW 207

cloudspider

score 66

先日のプログラミングコンテストに初めて提出したコードの復讐をするために、
計算量オーダーを算出したいと思っています。
以下のように計算したのですが、合っているかどうかの添削をお願いします。

count = 0
for i in range(n):
    for k in range(i+1,n+1):
        if sum(s[i:k]) == 0:
            count += 1

 計算手順

まずif文を無視するとforの二重ループは
\sum_{k=1}^{n}k = \frac {1}{2}n(n-1)
という風に計算できるので、
1/2 * O(n^2 + n) = O(n^2)
となります。

(teratailでの数式の記述の仕方がわかりませんでした。読みにくくてすいません)

特にわからないのはif文の条件式の部分ですが、
sum()とsliceのオーダーの求め方が合っているかわかりません。

このサイトを参考にするとsliceはO(k)だそうなので、
全体で見るとsliceの部分は、
\sum_{k=1}^{n}\sum_{l=1}^{k}l = \frac {1}{6}n(n+1)(n+2)
となるので、O(n^3)。

sum()も要素数でしょうか、
だとすると、上と同じ計算でO(n^3)。

よって、O(n^2) + 2O(n^3) = O(n^3)
とてもめちゃくちゃな計算になっている気がします・・。

よろしくお願いします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • Do_you_1isten

    2018/05/01 14:39

    sliceの中身に詳しくないのですが、参考にしているサイトでばO(k+n)になっていますが、sliceのnは考慮しなくてもいい感じですか?

    キャンセル

  • cloudspider

    2018/05/01 16:19

    すいません。よくわからないまま「Get Slice」の欄を見てO(k)にしたのですが、この場合だと「Set Slice」を見るのが適切なのでしょうか

    キャンセル

回答 2

+3

ランダウ記号は、無限大まで大きくした場合にどのようなふるまいになるかを考えるものなので、

  • 高次の項がある場合、それより次数の低い項は無視できる
  • 定数項は無視できる

ようなものです。

O(3n^2+2n+1)=O(n^2)というようにできます。

(なお、teratailの入力に数式モードはなさそうです)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/01 16:34

    ありがとうございます。
    それは知っていたのですが、自分の計算方法が合っているのかどうかがわからないので、質問させていただきました。

    キャンセル

checkベストアンサー

+1

count = 0
for i in range(n):
    for k in range(i+1,n+1):
        s_ = 0
        for j in range(i, k):
            s_ += s[j]
        if s == 0:
            count += 1


だと思うと三重ループになっていることがはっきりするのではないでしょうか。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.76%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • アルゴリズム

    381questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。