[B! qiita][big-o-notation] nabinnoのブックマーク

nabinno id:nabinno

qiitaとbig-o-notationに関するnabinnoのブックマーク (4)

計算量オーダーの求め方を総整理！〜どこから log が出て来るか〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か～文系理系問わず楽しめる精選 6 問～アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
nabinno 2021/04/01
qiita

algorithm

big-o-notation

performance-engineering
リンク
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita
0. はじめに気軽な気持ちでプログラムを書いたら計算量オーダーが $O(n^2)$ になってしまって処理がメチャクチャ遅い、というのは大変あるあるです (この記事など)。そういった状況を打破するために、古来から $O(n^2)$ なアルゴリズムを $O(n)$ や $O(n\log{n})$ に改良するテクニックは無数に考案されて来ました。逆に本来なら $O(n)$ で終わるはずの処理を雑に実装したために $O(n^2)$ になってしまうトラップも無数に知られています。その辺りの話は以下に特集してみました: 特集！知らないと損をする計算量の話今回は $O(n^2)$ を $O(n)$ にするテクニックの 1 つであるしゃくとり法について、個人的に思うことを書いて行きます。またしゃくとり法を用いる以下の問題たちを紹介します: AOJ Course The Number of Window
nabinno 2020/07/27
qiita

atcoder

big-o-notation

algorithm
リンク
計算量オーダーについて - Qiita
プログラムの計算量を表すO記法について、使用例を調査しました。計算量（オーダー）とは？あるアルゴリズムを使った演算の性能を表す指標。計算量は大きく二つに分けられる。時間計算量（処理時間の計算量）空間計算量（メモリ使用量の計算量）単に計算量（オーダー）と言った場合、時間計算量のことを指す。 O記法（オーダー記法）特定のアルゴリズムでの計算が、どれくらい掛かるかを表した記号。処理対象のデータが非常に大きくなった時の処理時間を大雑把に評価する。処理時間が短い順（性能が良い順）に代表的なオーダーをまとめる。 O記法概要使用例
nabinno 2018/06/17
qiita

big-o-notation

performance-engineering

mathematics
リンク
[初心者向け] プログラムの計算量を求める方法 - Qiita
はじめにこの記事では、プログラムの計算量を求める方法を説明します。プログラミングの初心者向けに、厳密さよりも分かりやすさを優先して説明していきます。サンプルコードについてこの記事のサンプルコードは、C言語（C99）で記述しています。計算量とは？計算量とは、「そのプログラムがどれくらい速いかを大雑把に表す指標」です。もう少し正確に言うと、「入力サイズの増加に対して、実行時間がどれくらいの割合で増加するかを表す指標」です。グラフによる計算量の表現計算量をグラフで表すと、以下のようになります。これは、「入力サイズ $n$ が増加するにつれて、実行時間が $n$ に比例して増加する」ということを表しています。別のグラフも見てみましょう。これは、「入力サイズ $n$ が増加するにつれて、実行時間が $n^2$ に比例して増加する」ということを表しています。計算量を求め
nabinno 2017/10/21
qiita

big-o-notation

algorithm

performance-engineering
リンク
1