[これが符号化テストである]第2講アルゴリズム性能評価

📍 複雑さ

時間複雑度:アルゴリズム実行時間の複雑度

空間複雑度:アルゴリズムメモリ使用量の複雑度

→複雑度が低いほど良いコード

📍 複雑度マーク方法

大文字(Big-O)
→関数の上限のみ保持
ex)演算回数3 N**2+5 N+10000000のアルゴリズムO(N**2)

📍 複雑度の順序

ますます複雑になる

1.O(1):一定時間

2.O(logn):ログ時間

3.O(N):線形時間

4.O(Nlogn):ログ線形時間

5.O(N**2):サブタイム

6.O(N***3):三次時間

7.O（2＊＊N）：指数時間

ex.

array = [3, 5, 1, 2, 4]  # 데이터 개수 N = 5
summary = 0

for x in array:
	summary += x

print(summary)

実行時間はデータ数Nに比例する
⇒ O(N)
ex.

array = [3, 5, 1, 2, 4]  # 데이터 개수 N = 5

for i in array:
	for j in array:
		temp = i * j
		print(temp)

⇒ O(N**2)
(すべての重複文がO(N**2)の時間的複雑さを有するわけではない)

📍 アルゴリズムせっけいそう

1.一般的に5億回を超えるとPythonは5～15秒かかる

◇コードテスト時間制限:1~5秒
◇時間制限が明確に規定されていない場合は、約5秒後に解除

2.PypyはCより速い場合があります

*Pythonコードがタイムアウトと判定された場合は、Pypyを再発行してみてください

3.優先確認時間制限

◆データ個数がN、時間制限が1秒の場合
N≦500:O(N＊＊＊3)アルゴリズム設計;
N≦2000:O(N＊＊＊2)アルゴリズム設計;
N≦100000:O(Nlogn)アルゴリズム設計;
N≦1000000:O(N)アルゴリズム設計

📍 アルゴリズムのトラブルシューティングプロセス

文章とコンピュータ事故を読む

需要(複雑度)分析

問題解決の構想を探す

ソースコード設計、符号化

※コアクリエイティブ→簡潔なコード作成が可能

📍 実行時間計測ソースコード

import time

start_time = time.time()

### 소스코드 ###

end_time = time.time()

print("time: ", end_time - start_time)

📍 ソース

これは就職のためのコードテストで、Python-羅東彬と