特集！知らないと損をする計算量の話 - Qiita
1. はじめに 今回は実務プログラミングにおいて知らず知らずのうちに遅いコードになっていそうな例をいくつか挙げて、それを計算量の観点から高速化してみたいと思います。 2. 計算量を意識することにどんな意味があるか 身近な例として、Qiita Contribution ランキングの作成を考えてみましょう。ランキングを作成するためには、各ユーザーの Contribution 数を大きい順に並び替える処理、すなわちソートが必要になります。 Qiita ユーザー数は現在およそ $30$ 万人です。標準ライブラリの sort を用いれば、それほどの計算時間はかからないと思います。しかし仮にこれを愚直な sort アルゴリズム (例えば、挿入ソートやバブルソートなど) で実行したら恐ろしいことになります。 愚直なソートは、並び替える要素の個数の 2 乗に比例した時間がかかります。すなわち $n$ を並
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実問題で登場する二部マッチングは以下のように多岐にわたります: マッチングアプリで男女のペアを最適化する (「男」と「女」) インターネット広告分野で、ユーザの興味に合う広告を出す (「ユーザ」と「広告」) 企業検索サービスなどで、ユーザの検索履歴に合う企業を
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
