矩陣矩陣複雜度

Question

我必須計算搜索矩形矩陣元素的算法複雜度。它使用分而治之。對於方陣，我的時間函數變成a * T（n/b）+ O（n^2）。但是對於矩形矩陣，如果必須將它劃分爲4個子矩陣，我不知道如何表示分割。它會是* T（m * n/4）+ O（n）？

Answer 1

你沒有描述你的算法，所以不可能精確地回答這個問題。但我會嘗試假設算法是這樣的：

1. 如果m = 1或n = 1然後處理矩陣O(m * n)時間。
2. 品（m > 1和n > 1）分矩陣劃分成大小爲不多然後[m/2]x[n/2]，其中[y]是最小的整數不小於y四個matricies。
3. 用這些矩陣中的每一個調用算法。然後「合併」結果在O(m * n)時間。

在用於時間複雜這種情況下經常方程將是

1. T（1，N）= O（n）的
2. T（米，1）= O（M）
3. T（M，N）= 4 * T（[M/2]，[N/2]）+ O（m * n個）

允許解決它

T(m, n) = O(m * n) + 
      4 * O([m/2] * [n/2]) + 
      4^2 * O([m/4] * [n/4]) + 
      ... + 
      4^L * O([m/2^L] * [n/2^L]), where L = [log(min(m, n))] 
T(m, n) = O(m * n + ... + 4^L * [m/2^L] * [n/2^L]) = 
     = O(m * n + ... + 2^L * [m/2^L] * 2^L * [n/2^L] = 
     = O(m * n + ... + m * n (L times)) = 
     = O(L * m * n) = O(m * n * [log(min(m, n))]) 

所以問題的答案是

T（M，N）= O（M * N * [日誌（分鐘（M，N））]），其中log代表一個以2爲底的對數和[y]代表ceil功能。