【O(n)】計算量の評価方法について【O(log n)】

**デフォルトの名無しさん** · 2013/03/21(木) 17:35:37.80

論文を仕上げるときに欠かせない計算量の考察
ランダウ表記というのがあるそうですが
計算量算出の根拠とかコツとかについて語り合いましょう

関連スレ
O（n)のソートアルゴリズムを発見した
http://toro.2ch.net/test/read.cgi/tech/1212217022/

参考
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7

**デフォルトの名無しさん** · 2018/07/08(日) 14:27:51.99

>>79
> この n と n*log(n) の差を無視できないなら

上の両者の比はnがどんどん大きくなれば幾らでも大きくなるが

> そもそも n と 100*n の差を無視するのもダメじゃないかと思う

この両者の比はnがいくら大きくなっても100のまま（100に収束するというべきか）

１行目と２行目とではnをどんどん大きくした時の漸近的挙動が全く違うのよ
その違いを理屈として理解する以前に感覚として納得できないならば、君には計算量に関するセンスが決定的に欠落している

**デフォルトの名無しさん** · 2018/09/30(日) 20:17:50.44

てｓｔ

**デフォルトの名無しさん** · 2019/05/22(水) 12:11:36.06

何に使ってますか？