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

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

新規登録して質問してみよう
ただいま回答率
85.35%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

689閲覧

AtCoder Beginner Contest 159 D 問題

tam1006

総合スコア28

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2020/04/10 07:30

前提・実現したいこと

AtCoder Beginner Contest 159 D 問題をPythonで解いているのですが,TLEになってしまいます。
このコードはforループが2つ,どちらもO(n)なので,全体としてもO(n)のはずなのですが,なぜTLEになってしまうのでしょうか。
見たところ,.countが負荷が大きいコマンドなのでしょうか。
他の方の解答を見て,この問題の解法は分かったのですが,なぜ自分のコードでTLEになってしまうのかが良く分かりません。

発生している問題・エラーメッセージ

O(n)のはずなのにTLEを起こしてしまう。
そもそもO(n)でないのか,何かのコマンドが負荷が大きいものなのか,原因を教えてください。

該当のソースコード

Python

1n = int(input()) 2a = list(map(int, input().split())) 3 4def cmb(n): 5 return int(n*(n-1)/2) 6 7goukei = 0 8count = 0 9 10for i in range(n): 11 if a[i] in a[:i]: 12 continue 13 else: 14 count = a.count(a[i]) 15 goukei += cmb(count) 16 17for i in range(n): 18 print(goukei - (a.count(a[i]) - 1)) 19

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

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

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

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

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

guest

回答1

0

ベストアンサー

list.countは線型探索を行います。
O(n)の処理がループ内に入っているので、これはO(n^2)ですね。


また、 a[i] in a[:i] も定数時間では実行できません。

投稿2020/04/10 07:34

編集2020/04/10 07:38
LouiS0616

総合スコア35668

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.35%

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

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

質問する

関連した質問