【シプサ】7 時間の複雑さ

気分一新、第三巻。

• asymptotic: asymptote 漸近線
  
• 漸近線: ある曲線が、原点から無限に遠ざかるにつれて、限りなく近づいてはいくが、決して交わらないし、接しもしない直線。
  
• おお。big-O記法というのは、大きい入力における近似の考え方だったんだ。
  
• うーん。logがわからない。wikipedia。。。
  
  
  
  • 任意の正の実数x について、x=a^p (a != 1) をみたす実数pが唯一存在する。このpを p = log[a] x と書く。
    
  • ここで、aを底と呼ぶ。底は、2, e(ネイピア数), 10などをとることが多い。それぞれのとき底を省略するために、Log, ln, lgなどと書くこともある。
    
  • xy = a^pのときp=log[a](xy)。x=a^q, y=a^rのときq=log[a]x,r=log[a]y。xy=(a^q)(a^r)=a^(q+r)だから、log[a](xy) = log[a]x +log[a]y。
    
  • nが自然数のとき、前項をつかって、log[a](x^n) = nlog[a]x。これはたぶん実数でもなりたって、log[a](x^p) = plog[a]x。
    
  • (log[a]x)(log[b]a) = log[b](a^(log[a]x)) = log[b]xより、log[a]x = (log[b]x)/(log[b]a)。なるほど定数倍だ。
    
  
  
• 5n^3+2n^2+22n+6 = O(n^3)。
  
  
  
  • nが十分大きければ、n^3 > 2n^2+22n+6。
    
  • よって、nが十分大きければ、6n^3 > 5n^3+2n^2+22n+6。
    
  
  
• 3nlog[2]n+5nlog[2]log[2]n+2 = O(nlogn)
  
  
  
  • loglognはlognよりもはるかに発散が遅い。ゆえにnが十分に大きければ、4nlog[2]n>3nlog[2]n+5nlog[2]log[2]n+2。
    
  
  
• O(n^2)+O(n) = O(n^2)。
  
  
  
  • nが十分に大きければ、定数倍の値に関わらず、O(n^2)+O(n^2) > O(n^2)+O(n)。
    
  
  
• f(n)=2^(O(n))の意味は?
  
  
  
  • nが十分に大きいとき、2^(Cn)がf(n)の上界になっているということ。
    
  • なんで、O(2^n)ってかかないんだろう??
    
  
  
• f(n)=2^(O(logn))の意味は?
  
  
  
  • nが十分に大きいとき、2^(Clogn)がf(n)の上界になっているということ。2^(Clogn) = 2^(log(n^C)) = Dn^Cだからn^Cが上界ということ。
    
  • なんで、O(n^C)と書かないんだろう?
    
  
  
• n^O(1)とは?
  
  
  
  • O(1)は、定数より大きくならない。よって、n^C。なので2^(O(logn))と同じ。
    
  
  
• n^5、n^3、nなどの上界を多項式境界という。
  
• 2^(n^6)、2^(n^2)、2^(n)などの上界を指数境界という。
  
  
• small-o 記法。
  
• f(n)=o(g(n)) <=> lim f/g = 0 。 なるほど。これはbig-Oよりも「ずいぶん大きい」境界だな。
  
  
• あ、big-Oとかsmall-OのOって、たぶんOrder(規模)のOなんだろうな。なっとく。
  
  
• う、言語0^k1^kの修正アルゴリズムで、走査回数がたかだか1+log[2]nになるのがわからない。考える。
  
  
  
  • n=2、01とのき。q01#Xq1#Xxq_#Xqx_#qXx_#qXx_。これは5回?
    
  • 1 + log[2]2 = 1 + 1 = 2。あり?
    
  • n=4、0011のとき。q0011#Xq011#X0q11#X0xq1_#X0x1q_#X0xq1_#X0qx1_#Xq0x1_#qX0x1_#Xq0x1_#Xxqx1_#Xxxq1_#Xxxxq_#Xxxxq_。これは13回?
    
  • 1 + log[2]4 = 1 + 2 = 3。あり?
    
    
  • なんかおかしい。1+lognになるのはここではないのかな?
    
  • まず、はしからはしまでの一回の動作のステップは、常にn。
    
  • じゃあ、何回、はしからはしまでをやりますか、というと、
    
  • n=2のとき、1回。log[2]2 = 1
    
  • n=4のとき、2回。log[2]4 = 2
    
  • n=6のとき、2回。log[2]6 = 2.58
    
  • n=8のとき、3回。log[2]8 = 3
    
  • n=10のとき、3回。log[2]10 = 3.32
    
  • n=16のとき。log[2]16 = 4
    
  • 1を足しているのがよくわからないが、対数的にはなっている。
    
  • なぜ、底を2とした対数的になっているのか?
    
  • 底を2とする対数ってなんだ?
    
  • a = log[2]b のとき、2^b = a。
    
  • そうか、今あるNがあるとき、「2の何乗がNですか」ということは、「Nに1/2を何回掛けると1になりますか」ということであり、これは「N個の作業対象があり、毎回作業対象が前回の半分になるときに、何回作業すると作業対象が0になりますか」ということと同義なんだ。
    
  • やっと、毎回半分になる作業が、log[2]n回の繰返しになるということが理解できた。
    
  
  

最後ぐだぐだになったが、とりあえず7.1がおわった。
次回は、7.2 クラスP。こつこつ。