アルゴリズム

データ構造 Part.0 「データ構造とは」

はじめに この記事では、データ構造の概要について説明いたします。 今後は色々なデータ構造について紹介していく予定です。 また、この記事の内容をまとめた動画をYoutubeに投稿しております。 よければそちらも確認してみてください。 youtu.be 目次 前提…

オーダー記法 Part3 「計算量の導出」

概要 この記事では計算量の導出について紹介します。 オーダー記法シリーズの中でも最も面白く、知るべき内容だと思います。 この記事では特に線形探索と二分探索の計算量を導出します。 この2つの導出を見るだけでも、基本的なテクニックが詰まってますので…

オーダー記法 Part2 「オーダー記法と計算量の比較」

概要 この記事では「オーダー記法」と「計算量の比較」について説明します。 また、記事の内容は動画でも紹介していますので、よければ確認してください。 youtu.be オーダー記法とは オーダー記法は計算量を数学的に記述する方法です。 まずは具体例から紹…

オーダー記法 Part1 計算量の種類

概要 ここでのオーダー記法は、アルゴリズムの性能(計算量)を評価するために使うものとします。 特に、あるアルゴリズムで問題を解く(計算する)際にかかる時間などの性能を表現できます。 ここからは、次のキーワードがでてきます。 もしまだご存知ない…

二分探索と線形探索のアルゴリズム

概要 二分探索と線形探索は、リスト探索という問題を解く方法(アルゴリズム)の一種。 リスト探索という問題は、基本的で理解しやすい問題です。 そのため、アルゴリズムの重要性を学ぶのに最適だと思います。 プログラマーでもアルゴリズムを意識する機会…

フィボナッチ数列の第k項をO(log n)で計算しようとしたけど難しかった話

目次 フィボナッチ数列 ビネの公式 計算誤差について 計算の工夫 最終的な計算時間 サンプルコード 1. フィボナッチ数列 フィボナッチ数列は、イタリアの数学者レオナルド・フィボナッチの名前をとって名付けられた数列です。 数列の決まりは、「ある項は、1…

フィボナッチ数列は再帰で実装するな

目次 この記事の目的 フィボナッチ数列 再帰で実装 ループで実装 計算時間の違い まとめ 1. この記事の目的 プログラミング経験者って、なんだかんだでフィボナッチ数列を実装したことがありますよね。 みなさんはどのように実装しましたか?覚えてらっしゃ…

【Java】2つの線分の交点を求める

目次 この記事の目的 x, y-平面上の線分を表すクラス 2つの線分の交点をもとめる方法 まとめ 1. この記事の目的 この記事では2つの線分の交点を求める方法を紹介します。 そのために必要になる、線分を表すクラスのコードも紹介します。 サンプルコードを上…

【Java】2つのベクトルがなす角度を求める

目次 この記事の目的 三点がなす角度の求め方 x,y-平面上の座標を表すクラス ベクトルの差、長さ、内積、外積 三点がなす外角を求める まとめ 1. この記事の目的 この記事では、xy-平面上の点の情報から角度を求める方法について紹介します。 特に、三点を…

【WebAssembly】JSとwasmでソートの速度を比較する

目次 この記事の目的 C++でソートを実装 JSでソートを実装 実行用のHTMLを準備する 実際に速度を比較する まとめ

C言語でクイックソート

クイックソートとは クイックソートとは、O(n*log(n)) ソートの一つ。比較ソートの中では最も高速なアルゴリズムの一つ。再帰を用いるアルゴリズムなので、停止条件(ベースケース)の実装を忘れずに。詳しくは クイックソート - Wikipedia を参照してくださ…