ひとつの多重集計アルゴリズムの分析のテーマ

N本の長さがすべてMの秩序チェーンテーブルをマージし、マージ後のチェーンテーブルも秩序を保ち、時間の複雑さは(?)?A.O(N*M*logn)B.O(N*M)C.O(N)D.O(M)はAの牛客上の問題に答え、philianが集計アルゴリズムで解くことを提案し、まず集計アルゴリズムの時間複雑度に答えた.1つ目の解法:

T(1) = 1
T(n) = 2T(n/2) + n
T(n/2)/(n/2) = T(n/4)/(n/4) +1
T(n/4)/(n/4) = T(n/8)/(n/8) +1
.
.
.
T(2)/2 = T(1) +1

左側右側をそれぞれ加算し、消去してT(n)/n=T(1)+logn=>T(n)=nlogn+n=O(nlogn)の第2の解法を得る.

T(n) = 2T(n/2) + n
2T(n/2) = 2(2(T(n/4))+n/2) = 4T(n/4)+n
T(n) = 4T(n/4) + 2n
4T(n/4) = 4(2(T(n/8))+n/4) = 8T(n/8)+n
T(n) = 8T(n/8)+ 3n
   
T(n) = 2^k(n/2^k) + kn
  k=logn
T(n) = nT(1)+nlogn = nlogn + n

本題に戻ると,長さMのサブシーケンスが秩序化されているため,上述したnから1までの再帰を一括し,Mから1までの再帰部分を一括して切り取ることに相当するため,一括した時間複雑度でこの一括を削減する必要がある.n=N*Mであるため、1に再帰すると、時間複雑度はO(N*M*log(N*M))、n=Mであると、1に再帰する時間複雑度はO(M*logm)となり、Nセグメントというサブシーケンスが共有されるため、加算するとO(N*M*logm)の時間が前後に減少し、O(N*M*log(N*M)−N*M*logm)=O(N*M*logN)となる