計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita

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

[HHR]

超大作。よくもこんなに例を集めたと脱帽

[smokeymonkey]

なるほど全然わからん。数学的概念苦手すぎる。

[cj3029412]

頭いいー(*'▽') 参考になります! 🐈💕

[tena-beji]

“O(logn)O(log⁡n)”

[kwhrtsk]

めっちゃ分かりやすいまとめ

[t_f_m]

あとで

[calibaby]

初心者的には、まだまだ問題が解けるだけでめちゃくちゃはしゃいじゃうくらい嬉しいんだけど、こういうところも計算して意識していけるようになろうっと。少しずつ。

[oinume]

計算量についてわかりやすい

[akaboha]

“計算量オーダー”

[anatofuz]

コード例がこんなに載ってるのすごいな

[Taniken]

“今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのよう

[hogege]

設計時に参考にする:-P

[makaya]

や

[tmatsuu]

良い。あとで読み直す

[Iridium]

タイトルが壊れるのはなんで？

[dmutaguchi]

“正の整数nが3の倍数か、または3の付く数字であるかどうかを判定”する問題を「ナベアツ」と呼ぶのか！

[koroharo]

“計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜”

[kazoo_oo]

これは大作。しかもわかりやすい。

[zou3dazou]

オーダによってどれくらいのサンプル数であれば実行可能のまとめなど

[skypenguins]

分かりやすい

[akymrk]

"計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜"

[takehikom]

昔書いたの http://d.hatena.ne.jp/takehikom/20080608/1212877319 よりうんと丁寧／二進法展開はO(|n|)と書き入力長に比例というのが自分の感覚

[mixedjuicegofyugofyu]

計算量