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

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

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

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

Q&A

解決済

1回答

383閲覧

このコードの計算量はO(N^3)ですか?

takey

総合スコア312

アルゴリズム

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

0グッド

0クリップ

投稿2019/09/12 00:50

Python3 のコードです。

python

1N = 100 2A = [0]*N 3 4cnt = 0 5for i in range(N): 6 for j in range(N): 7 if i == j: continue 8 9 left, right = min(i, j), max(i, j) 10 M = len(A[left: right+1]) 11 12 for k in range(0, M, 2): 13 cnt += 1 14 15print(cnt)

上記のコードの全体の計算量は O(N^3)であってるでしょうか。

python

1 for k in range(0, M, 2):

の部分の計算量が O(N) になると思うので、全体の計算量はO(N^3)だと思うのですが、あってるでしょうか。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

はい、特に最適化などかけていなければ、ループはループのままなので、オーダーはO(N^3)です。


9/13追記:出力だけが目当てなら、次の式を使えば、O(1)にすることが可能です。

python3

1N = 100 2cnt = ((N-1)*N*(N+7))//6 - (N*N)//4 3print(cnt)

なぜこれで計算できるのかは、そこまで難しい話でもないので、投稿者さんの課題ということにしておきます。

投稿2019/09/12 10:01

編集2019/09/13 01:39
majiponi

総合スコア1720

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

takey

2019/09/14 09:23

どちらかというと、cntの計算がしたいわけではなく、`for k in range(0, M, 2):` の部分の計算量の算出方法が知りたくて説明しました。そういう意味では、cntの計算をするようなコードの書き方が悪かったですね。(do_something()とかにすればよかったです) Teratailに投稿したモチベとしてはまあ少なくとも当該コード部分はO(logN)じゃないだろうし、だったらO(N)かな。でも自信ないな。そうだTeratailで質問しようといった感じです。でも、ご回答ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問