こんにちは。倉内です。
アルゴリズムを学ぶ際に理解しておきたいのが、計算量とO記法（オーダー記法）についてです。
ただ、「聞いたことはあるけどよく分からない…」「数学の知識が必要で難しそう」というイメージを持っている方もいるかもしれません。
そこで今回は、paizaラーニングに新しく追加された、計算量の基本的な概念と、よく登場する具体的な例を動画で学べる講座「新・アルゴリズムとデータ構造入門 Java編3: 計算量の見積もりとO記法」をご紹介します。計算量が分かると、データ量に対するより効率的なアルゴリズムを考えたり、採用するアルゴリズムの性能を評価したりできるようになります。
動画での解説と問題集を使った実践を通して、プログラミング初学者の方も一緒に学んでいきましょう！
そもそも「計算量」とは？
計算量とは、簡単に言うと計算にかかるコストの指標です。
計算量には空間計算量と時間計算量があり、プログラムの処理時間について扱う場合は時間計算量を指します。処理が終了するまでに必要とする命令数はどのくらいかで見積もることができます。
時間計算量を表現する方法として、O記法（オーダー記法）というものが使われます。ランダウの記号とも呼ばれます。オーダーは、あるアルゴリズムがどれくらいの処理時間がかかるかを評価するものです。具体的には、O(N) や O(N^2) といった形で表記されます。
O表記の代表例や計算量の比較については、以下の記事で詳しく解説しています。興味がある方はごらんください。
動画講座「計算量の見積もりとO記法」
paizaラーニングの講座「新・アルゴリズムとデータ構造入門 Java編」では、現在3レッスン公開しています。
1：アルゴリズムとデータ構造
プログラミング初心者の方も理解しやすいよう、基礎知識として、アルゴリズムとはなにかデータ構造とはなにかを学びます。
2：線形探索
探索アルゴリズムについて知り、その中でも線形探索について学習します。
3：計算量の見積もりとO記法
計算量の見積もりとO記法について学習します。本記事ではこのレッスンについて詳しく取り上げます。
3つのチャプターからなり、まずチャプター1でO記法とはなにかを学びます。ここでは計算量の見積もりの観点について理解することが大切です。
次にチャプター2でO記法を用いた具体的な計算量の導出について学びます。
数学の話になってくるので少し抵抗がある方もいるかもしれませんが、動画では具体例を挙げてていねいに説明していますので、理解しながら進めてみてください。
チャプター3では、典型的な計算量について、入力データのサイズが増えたときにどうなるかで計算量を考えていきます。計算量を見積もった結果、そのアルゴリズムが現実的な時間で実行可能かどうかを評価する際には、コンピュータの処理速度を知っておく必要があります。
入力されるデータのサイズが小さいときはどのアルゴリズムを採用でもあまり計算量に差がなかったとしても、サイズが大きくなったときに計算量にかなり差がある場合もあります。そうすると処理の実行が現実的な時間で終わらない可能性が出てきます。
「レベルアップ問題集」で実践する
paizaでは、プログラミングの練習問題を集めた「レベルアップ問題集」を公開しています。
ループや条件文、配列といった基本文法をおさらいできる問題から、ソート、線形探索、木やグラフなどアルゴリズムに関する問題、そしてスキルチェック*1の過去問まで多様な練習問題があり、難易度もさまざまです。
ソートアルゴリズムの問題集
問題集の中で、計算量について理解を深めるにあたっておすすめしたいのが、ソートアルゴリズムの問題を解くことです。
ソートとは、昇順・降順・アルファベット順・日付順などなんらかのルールにのっとって、数値や単語といったデータを並べることを言います。
たとえば、数字であれば不規則な並びより1, 2, 3…と順に並んでいたほうが人間は扱いやすいですが、コンピュータも同様に何か処理をするときは、ソートされたデータに対してのほうが効率よく処理ができます。
そのデータをソートする際に用いられるのがソートアルゴリズムです。隣接するデータの大小を比較して入れ替えたり（バブルソート）、全データをまず分割して最小単位でソートしてマージをしたり（マージソート）いろいろなやり方があります。そのやり方によって計算量が異なります。
レベルアップ問題集では「素朴なソートアルゴリズム」として挿入ソート、選択ソート、バブルソートを扱っています。また、「効率的なソートアルゴリズム」としてシェルソート、マージソート、クイックソートを扱っています。
解答例・解説のある言語：Python3、Java、C++
解答例・解説のある言語：Python3、Java、C++
問題文の冒頭には扱うソートについての説明がありますので、ソートに詳しくなくても取り組むことができます。問題集を通して理解を深めてみるのもよいでしょう。
探索アルゴリズムの問題集
他には探索アルゴリズムの問題もおすすめです。探索とは目的のデータを配列やリストなどに格納された複数のデータの中から探すことをいい、こちらも採用する方法によって計算量が変わってきます。ちなみに、さきほど紹介したとおり、動画講座のレッスン2は線形探索に関する内容になっています。
レベルアップ問題集では、線形探索、二分探索、幅優先探索・深さ優先探索の問題を解くことができます。
解答例・解説のある言語：Python3、C#、C++
解答例・解説のある言語：C++
解答例・解説のある言語：C++
解答例のある言語は限られますが、解説は問題を解く方針を記載しているためどの言語で解く場合でも参考になると思います。ぜひごらんください。
まとめ
動画講座の新レッスン「新・アルゴリズムとデータ構造入門 Java編3: 計算量の見積もりとO記法」と、計算量について理解を深めるための練習問題を紹介してきました。
計算量を考慮したプログラムが書けると、paizaのスキルチェックのS・Aランクの高ランク問題でデータ量の多いテストケースをパスできるようになります。実力を試したい方は挑戦してみてください！
詳しくはこちら
なお、paizaラーニングでは、アルゴリズムに関する講座はもちろん、プログラミング学習を始めたばかりの方向けの入門講座や、Webフレームワークを使ったアプリケーション開発の講座なども多数公開しています。ブラウザさえあれば、今すぐプログラミングの基礎を学ぶことができます。
詳しくはこちら
*1:paizaが提供するプログラミングスキルを測るサービス。問題を解いた結果によって、S・A・B・C・D・Eの6段階で評価します。
