アルゴリズムとデータ構造 -No.1-
アルゴリズムとデータ構造の学習
就活が終わり、今後1年「TOEIC 800」・「アルゴリズム」・「Django & React」を大きな学習目標として立てました!!
と言うことで、アルゴリズムを学ぶ上でオススメされた
で学んだ内容を本ブログにまとめていこうと思います。
アルゴリズムとは
アルゴリズムとは、問題を処理するための操作手順です。
この本で紹介されていた、「問題に対する具体的な解を書き下すことができなくても、解を得るための「手順」を与えることができれば良い」と言う言葉が非常に印象的であり、これまでなんとなくプログラミングをしていましたがアルゴリズムを学ぶ事は非常に重要であると気づきました。
計算量とオーダー記法
計算量:アルゴリズムの良し悪しを測る重要な指標
この計算量により、コンピューター上での実行に要する時間を、大雑把に見積もることができるらしいです。これまで講義などで計算量について学ぶ機会はありましたが、いつも難しそうなイメージがへばりついており、なかなか積極的に触れてこなかったですがこの機会にしっかり学ぼうと思います。
オーダー記法(ランダウのO記法)
「アルゴリズムAの計算時間T(N)が概ねP(N)に比例する」ということを、T(N)=O(P(N))であると表し、アルゴリズムAの計算量はO(P(N))であるといいます。
代表的な計算ステップ回数の比較は以下の通りです。logなどが出てくるとどうも苦手意識が出てしまうのですが、ひとまずはこちらを覚えつつ理解しようと思います。
logN > N > N^2 > N^3 > 2^N > N!
- 指数時間アルゴリズム(exponential time):O(2^N) , O(N!)
Nの増加に伴い計算時間が急速に大きくなる
定数 d>0 が存在して計算量がN^dの定数倍によって上から抑えられる
N>=10^5 まで行くと膨大な時間がかかる
- 定数時間アルゴリズム(constant time):O(1)
問題の大きさに依存しない定数時間以内に処理が終わる
*データを雑に扱ってしまうとO(N)となってしまう場合がある
ちなみに、大体1秒間で処理できる計算ステップ回数は 10^9 回程度だそうです。
ランダウのO記法の詳細
- O記法:計算時間を上から抑えて評価
- Ω記法:計算時間を下から抑えて評価
- θ記法:計算時間を上からも下からも抑えるという評価
主には、O記法が用いられるそうです。
今日は第1章、第2章を学習しました。計算量については、外枠だけを学んだような感じなので実際にプログラムを組みながらつかんでいきたいと思います。