CLRS Chapter 4

CLRS

Introduction to Algorithms / アルゴリズムイントロダクション

Exercise 4.1-1

最大要素一つのみの配列

Exercise 4.1-2

def BruteForceMaximumSubarray ( A )
   max <- -1
   r <- 0
   l <- 0
   loop for i from 0 below A.length
      sum <- 0
      loop for j from i below A.length
         sum <- sum + A[j]
         if max < sum
            max <- sum
            r <- i
            l <- j
   return A[r .. l]

Exercise 4.1-3

n0 = 23だった。crossover pointは変えないが、全体的にrecursiveバージョンは速くなる。
面白いのがrecursiveの計算時間をTr(n)とおくと、Tr(n0) > Tr(n0 + 1)となったところ。bruteの計算時間をTb(n)とおくと、Tr(n0) = Tb(n0) , Tr(n0+1) = 2Tb(n0/2) + Theta(n)となり、Tb(n0/2)がTb(n)に比べて十分小さかったからだ。そこで、bruteに切り替えるのをn0/2 (13) にしたところ、recursiveバージョンはさらに速くなり、crossover pointはn0/2+1 (14)となった。

Exercise 4.1-4

元のアルゴリズムの返り値が正だったらそのまま。負だったら空配列を返すようにする。

Exercise 4.1-5

Figure4.1のPrice配列のようなものを作り、Price[0 .. i]の最小値をiについてそれぞれ計算していく。それとPriceの差のmaxを取る。