【独学するコンピュータサイエンス】計算量・データ型・ループ
代表的なアルゴリズムの計算量（暗記事項）
代表的なアルゴリズムを列挙します。
ロジックを設計する際に、どんなアルゴリズムを利用すればよいかの検討がつけられるようになるためには、これらを覚えてしまうのが手っ取り早いです。
【探索アルゴリズム】
線形探索法 O(N)
二分探索法 O(logN)
ハッシュ探索法 O(1)
【整列アルゴリズム】
バブルソート
選択ソート
挿入ソート それぞれO(N^2)
（ただし、挿入ソートはデータがあらかじめ昇順整列されている場合には、O(N)となります。なぜならM-1番目の要素<=M番目の要素という関係がすでに成立しているので、M番目の要素の処理における比較回数は1回で済むからです）
クイックソート
ヒープソート
マージソート それぞれO(NlogN)
というわけで、データは「探す」よりも「並べる」ほうが計算量が多くなることがわかります。現実世界に置き換えてかんがえてみると、どうでしょう。何かを探すことと、並べることのどちらのほうが大変だと思いますか？
各オーダーの比較
Oをつかったオーダー記法を理解したのはよいのですが、たとえばO(N)とO(logN)のどちらが大きいかという比較をするとして、正しく比較するには、データをグラフにプロットして比較する必要が出てきたりします。ちなみにNが十分におおきな場合にはO(logN)のほうが大きくなります。
こういう検討をするために逐一グラフ化するのも面倒なので、各オーダーの比較は暗記してしまうのが結果的に手っ取り早いです。
O(1)＜O(logN)＜O(N)＜O(NlogN)＜O(N^2)＜O(2^N)＜O(n!)
い（1）ろ（log）ん（N）NlogN 窒素（N^2）に（2^N）!
と覚えましょう。（語呂合わせへたくそか！）
自動変数とスコープ
ブロックの外と中で変数名が重複した場合はブロックの中が優先されます。
繰り返し命令内で自動変数を宣言する事はまずありません。繰り返しの回数だけ変数の領域確保、初期化、開放が行われるので、処理効率が非常に悪い為です。コンパイラーの最適化によってそうならない場合もあります。
今の場合では main 関数の先頭でもう一つ変数を用意しそれを繰り返し命令のブロック内で使用すれば、変数の領域確保、初期化、開放はそれぞれ一回で済みます。
繰り返し命令内で自動変数を使うぐらいなら繰り返し命令も含めて関数化した方が良いでしょう。
変数宣言とその初期化について
自動変数の宣言と初期化は同時に行ってはいない事です。自動変数の宣言はそのブロックの始めにするもので、宣言をしているブロックに入った時点で有効となり、そのブロックを抜けた瞬間に無効となります。
一方初期化は宣言ではなく命令に相当します。命令はそこに到達しない限り実行されません。
宣言と初期化は同時に行われない、これを知らないと思わぬバグを生み出してしまいます。
二項演算と型変換
二項演算ではより大きな項に型が揃えられる通常の算術変換が施されます。変数 i は int 型、d_dnv は double 型です。したがってたとえばint型とdouble型の和をとる計算の時に i の値は double へと自動的に型変換されます
ポインタが関わってくると、型変換はとても危険な行為になりうるので、注意をする必要があります。
ループ条件の先判断と後判断
最初に終了条件を判断する方式を先判断と呼び繰り返し内の処理を一度済ませてから条件判断する方式を後判断と呼びます。プログラム技法上極めて重要な概念です。
先判断は条件次第では繰り返し処理が一回も行われません。後判断はどんな条件であろうと少なくとも一回は繰り返し内の処理が行われます。どんな時にどんな手法を使うかはそれこそ千差万別、一概には言えません。こればかりは経験を積むしかないのです。
どちらを使っても良い場合もありますしどちらか片方でなければいけない場合もあります。両方使える場合は分かり易くそして簡潔になる方法を選択してください。それぞれの特性を活かし使い分けられるよう今から鍛えておきましょう。
** 無条件分岐gotoが種々の条件分岐系処理の根本的な処理です**
今回はここまで。
ではでは！