オーダって難しい

最初に覚えること
最初は流し読みしてOK。例題の部分をみて、最後に理解する。最初に理解できるんだったらそれでよし。
ここでは要素が2^k個の要素数についてのマージソート考える
計算時間をT(N)とする。ここでのT(N)とは、「要素数Nに対して、マージソートを行い整列」=T(N)とする。 集合Sを二分割=S1,S2にして整列する為の計算時間は、S1=T(N/2),S2=T(N/2)なので

T(N)=S1+S2=T(N/2)+T(N/2)+c*N となる。2^k=N個。又、要素数が1の場合、つまり、2^k=1個のときは、T(1)=S1+S2が無理なので、←要素数が1を二つに分割はできない。
T(1)=c' とする。

---

↑ c*Nのことがよくわからない。マージソートを行う際、すべての要素をコピーしないといけないので、要素数Nをコピーする時間=c*Nと考えた。あってるかはわからない。cは定数}
↑ 要素2個をマージソートする際に、

1. 1個の要素数になるまで分割
2. 1個の要素と1個の要素を比較して、大きさ2の新しい配列に要素をコピー→統合(整列ずみ)

という手順を踏むが、c*Nは2番の『要素をコピー』の計算時間のこと。

---

例題
要素数は2^k個です。

k=1  N=2(要素数2個)   T(N)=T(N/2)+T(N/2)+c*N=2T(N/2)+c*N
k=2  N=4   T(N)=2T(N/2)+c*N=2{T(N/4)+T(N/4)+c*(N/2)}+c*N=4T(N/4)+2*c*N
↓         {T(N)=T(N/4)+T(N/4)+T(N/4)+T(N/4)+c*N+c*N=4T(N/4)+2c*N}
※かけ算はc*N部分に演算はokだが、T(N/4)の部分にはだめ。関数Y(X)という式はXをかけるとX*Y(X)であって、Y(X^2)ではない。
なんでN/2がN=4でN/4になるのか?。知らない。要素数を1個まで分割しないといけないから自然とこうなる？のかな。

k=3  N=8   T(N)=T(N/8)+T(N/8)+T(N/8)+T(N/8)+T(N/8)+T(N/8)+T(N/8)+
                      +T(N/8)+c*N+c*N+c*N=8T(N/8)+3*c*N

続けていくと
k=k  N=2^k   T(N)=T(N/2^k)+T(N/2^k)+…+T(N/2^k)_2^k個です+k*c*N
            =2^k*T(N/2^k)+k*c*N
            =N*T(N/N)+k*c*N  ←N=2^kなので
            =N*T(1)+N*k*c
            =N*T(1)+N*logN*c  ←logN=log2^kよりlogN=kなので。logの底は2。
                        ここで底は書かないのが普通らしい。

最初の覚えることに戻るが、T(1)=c'と置いたので、
            =N*c'+N*logN*c
N*logN*cのcをN*c'より大きくなるように設定する。つまり N*c  <  N*logN*c''となるようにc=　c’’する。計算時間は次数の低いやつは無視できるので、
O(T(N))=O(N*c'+N*logN*c)=O(N*logN) となる。最後は曖昧な知識だからちゃんとした説明にはなってないかも。
クイックソートも似たようなもんだから同じでいいの?