計算量

こんにちは。倉内です。アルゴリズムを学ぶ際に理解しておきたいのが、計算量とO記法（オーダー記法）についてです。ただ、「聞いたことはあるけどよく分からない…」「数学の知識が必要で難しそう」というイメージを持っている方もいるかもしれません。そこで今回は、paizaラーニングに新しく追加された、計算量の基本的な概念と、よく登場する具体的な例を動画で学べる講座「新・アルゴリズムとデータ構造入門 Java編3: 計算量の見積もりとO記法」をご紹介します。計算量が分かると、データ量に対するより効率的なアルゴリズムを考えたり、採用するアルゴリズムの性能を評価したりできるようになります。動画での解説と問題集を…

計算量で対数時間 というものをよく見かけると思いますが、これが具体的にどの程度のものか、感覚で理解してみます。 まず大前提として、 の底は（計算機科学においては一般に）2 です。何故 2 なのかというと、分割統治法の考え方で問題サイズを半分にすることを繰り返すことが多いからです。ここから計算回数 という値が出てきます。 対数時間の感覚的な掴み方ですが、対数関数は指数関数の逆関数です。 指数関数 は（1より大きい自然数の底 を前提として）、 が増加するほど爆発的に が増加します。指数関数の爆発性は、「紙を 回折りたたむと高さ何メートルになるか？」といった例で有名です。 ここから考えて、逆に、対数…

アルゴリズムとデータ構造の学習 就活が終わり、今後1年「TOEIC 800」・「アルゴリズム」・「Django & React」を大きな学習目標として立てました！！ と言うことで、アルゴリズムを学ぶ上でオススメされた bookclub.kodansha.co.jp で学んだ内容を本ブログにまとめていこうと思います。 アルゴリズムとは アルゴリズムとは、問題を処理するための操作手順です。 この本で紹介されていた、「問題に対する具体的な解を書き下すことができなくても、解を得るための「手順」を与えることができれば良い」と言う言葉が非常に印象的であり、これまでなんとなくプログラミングをしていましたがア…

はじめに 『いもす法』ってなんぞや Pythonでの実装例 まとめ はじめに データサイエンスを日常的に行う中で大量のデータを扱うことが往々にしてあります．その際に頻繁に発生してくる問題が膨大な計算量による待ち時間発生や計算が有限時間内に終了しないといった問題です． 私は特にこの待ち時間を非常に厄介だと感じていてます． 何故かと言うと，待ち時間が発生すると当該処理が終わるまで別の作業をして効率的に物事を実施しようと思うのですが，逆にこのタスクの切り替えによってオーバヘッドがかかってしまい非効率になってしまうためです． 例えば，英語長文読解の勉強をしている途中で急に洗濯の依頼をされ，洗濯が終わっ…