プログラミングパラダイムとアルゴリズム
過去投稿のプログラミングパラダイムの記事と少し重複するところがありますが、
今回講義という形で復習したものからの学びとなります。
プログラミングパラダイム
プログラミングパラダイムはスタイルや方法である
リソース===作りたいもの
この仲介を担うものがプログラミングパラダイムです。
関数型プログラミング
例えば、X=3 Y=3なら常に答えは5という表示がされる。
メリット
・副作用が少ない
・テストがしやすい
・プログラムがわかりやすい
オブジェクト指向
部品を作って、部品を組み立てて車を作るイメージ
・クラス(オブジェクトを実装する型)
・インスタンス(クラスから生まれた実体)
・オブジェクト(状態を表すデータと振る舞いを表すメソッドで構成)
・メソッド(関数)
・プロパティ(変数)
メリット
・大規模なプログラムを書きやすい
・綺麗に書けば理解しやすいプログラムを書ける
・プログラムの設計に時間がかかる
・きれいに書かないと理解しにくいプログラムになる
アルゴリズム
アルゴリズムは課題を解決する際の思考法のことをいいます。
課題を解決する際の思考のパターンであったり、定石ともいえます。
また計算や作業を遂行するための手順のことです。
二大検索アルゴリズム
線形検索
リストや配列に入ったデータの検索を行う。
先頭から順番に検索を行って見つかったら終了する。
二分探索
ソート済みのリストや配列に入ったデータにおいて、
検索する間隔を半分に分割しながらデータを検索するアルゴリズム。
例(Python)
number=[1,10,5,4,2,7,3,9]
というものが与えられた際に、初めから数値を探索するという線形探索をする場合のコードになります。
for i in range(len(list));
if(list[i]==3):
print(i)
break
オーダー記法
アルゴリズムの性能を評価するための指標になります。
何秒処理にかかったのか。というのではなく、何ステップで処理できたのかを考察する過程になります。
以下幾つかの例になります。
O(1)
命令数がデータ数に比例する場合。
O(n)
命令数がデータ数に比例する場合。また、nに比例する回数以内のループ処理で終わる場合を指す。
例として、線形探索が挙げられます。
O(n^2),O(n^3)
2*n^2+4*n+5といった計算量があった場合は、nの最大時数を取る。この場合は2*n^2に注目する。
O(n^2)に関して、バブルソートなどが例になります。
O(logn)
データ数をnとします。この際に2をステップ数乗した値の定倍値が計算量になります。
また、対数を意味し、二分探索が主な例になります。
最後に
講師の方曰く、実際に自分でアルゴリズムを作ってみて評価されるのがいいとのこと。
HackerRankといったサイトで学習するといいとのことです。