原題來自雪梨教育
http://www.edu2act.net/task/list/checked/
題后給出講解和擴展
任務1_1 比較下列算法的時間復雜度
任務描述：
? ? 下面給出4個算法，請分析下列各算法的時間復雜度，請寫清楚題號，并將每個小題的分析過程寫出來，并給出分析結果。
（1）
for(i = 1; i <= n; i++)scanf("%d", &num[i]);
ans = num[1];
for(i = 1; i <= n; i++)
{for(j = i; j <= n; j++) {s = 0;for(k = i; k <= j; k++)s += num[k];if(s > ans)ans = s;}
}
（2）
for(i = 1; i <= n; i++)scanf("%d", &num[i]);
sum[0] = 0;
for(i = 1; i <= n; i++) {sum[i] = num[i] + sum[i - 1];
}ans = num[1];
for(i = 1; i <= n; i++) {for(j = i; j <= n; j++) {s = sum[j] - sum[i - 1];if(s > ans) ans = s;}
}
（3）
int solve(int left, int right)
{if(left == right)return num[left];mid = (left + right) / 2;lans = solve(left, mid);rans = solve(mid + 1, right);sum = 0, lmax = num[mid], rmax = num[mid + 1];for(i = mid; i >= left; i--) {sum += num[i];if(sum > lmax) lmax = sum;}sum = 0;for(i = mid + 1; i <= right; i++) {sum += num[i];if(sum > rmax) rmax = sum;}ans = lmax + rmax;if(lans > ans) ans = lans;if(rans > ans) ans = rans;return ans;
}int main(void)
{scanf("%d", &n);for(i = 1; i <= n; i++)scanf("%d", &num[i]);printf("%d\n", solve(1, n));return 0;
}
（4）
for(i = 1; i <= n; i++)scanf("%d", &num[i]);num[0] = 0;
ans = num[1];
for(i = 1; i <= n; i++)
{if(num[i - 1] > 0) num[i] += num[i - 1];elsenum[i] += 0;if(num[i] > ans) ans = num[i];
}
任務1_2 數字反轉的時空復雜度
任務描述：
下面兩個函數fun1和fun2都是實現對整數的逆序輸出功能，請根據下面題目要求，給出答案。
（1） 請分析函數fun1的時間復雜度和空間復雜度；
（2） 請分析函數fun2的時間復雜度和空間復雜度。
代碼如下：
?
int fun1(int n)
{int rev = 0;while (n != 0) {int pop = n % 10;n /= 10;rev = rev * 10 + pop;}return rev;
}void fun2(int n)
{printf("%d", n % 10);if(n / 10 != 0)fun2(n / 10);
}int main(void)
{printf("%d\n", fun1(10203)); fun2(10203);return 0;
}?
講解：
說頻度，或者求和公式往上堆出來的解釋，?都是耍流氓
沒有專業名詞的講解才是講解
?
直接粘貼我交的作業
?
先用數學說明，后解釋題意并分析。
分別為O(N^3),O(N^2),O(N*logN),O(N).
數學：
1）第一個循環O(N)
對于每一個i來說，j執行n-i+1次，對于每個j來說，k執行j-i+1次，我們把常數去掉，
對于每一個i，執行的常數操作為1+2+3+...+(n-i+1),等差數列[1+(n-i+1)](n-i+1)/2約等于(n-i)^2而i=1,2,....n，分別執行常熟操作次數為(n-1)^2,(n-2)^2......1^2,0^2.，可以看出是平方函數求和，而對x^2求和n項的公式為(n^3)/3+(n^2)/2+n/6，我們只看最大，去掉常數，也就是O(N^3).
O(N^3)+O(N)當然還是O(N^3)
2）前兩個循環都是O(N),下面兩重循環，對于每個i，j執行n-i次，當i=1，2....n，j執行次數為n-1,n-2....1,0,可以看出是等差數列求和，最高項是(n^2)/2，去掉系數，時間復雜度為O(N^2).
加起來：O(N^2)+O(N)+O(N)=O(N^2)
3）分析solve函數：采用二分，將序列分成兩份，直到不可再分，執行的兩個循環加起來就是遍歷一遍左右端點之間數的復雜度。我們看所有從長度為1的子數組，數量為n，合并后，所有長度為2的子數組，數量為n/2，再合并，長度為4的子數組，數量為n/4，我們會發現對于每個長度1,2^2,2^4,2^3，的子數組，遍歷一遍所有長度一樣的子數組的復雜度都是O(N)，設一共有x種長度，2^x=n,很明顯x=log(2,n)。
每次O(N)，次數o(log(2,n)),乘起來O(n*logn)
看main函數，接收數據是O(N)，加solve，等于O(n*logn)
4）接收數據O(N)，一個循環O(N)，加起來O(N)。
?
下面我根據完成的功能和思路分析一下：（思路簡單，文字略長，不太會敘述）
這四個代碼完成的功能都是求最大子數組（注意用詞準確，子數組連續，子序列可以不連續）。
1）分別枚舉每一個子數組的起點和終點，也就是i和j，對于每一個起點和終點，對中間部分求和，也就是k循環。顯然有n個起點n個終點（去重減半，不影響復雜度），所以子數組數量為O(N^2)，對于每個子數組，我們要遍歷一下求和，子數組長度1-n不等，遍歷一遍平均O(N)，乘起來O(N^3).（注意可能產生時間更大的錯覺）。找出所有子數組中最大的即可。
2）預處理出每一個以第一個元素開始，第i個元素結尾的子數組和，還是枚舉每個起點終點，但是我們求和時直接減就可以了，不用遍歷。對于每個子數組，操作為O(1),子數組數量O(N^2),所以總時間O(N^2).
3）二分，求左右兩邊最大子數組，取最大。但是還有一種情況：包含斷點的那些子數組也要考慮，請思考那兩個那兩個循環為什么那么寫？最后邏輯為何正確？
4）動態規劃入門思想
沒有枚舉，num[i]的含義是以下標i結尾的所有子數組中最大的。
遍歷數組，對于第i個元素，它的所有子數組下標范圍有[1,i],[2,i].....[i-1,i],還有它自己，我們看i-1個元素，他的子數組為[1,i-1],[2,i-1].....[i-1]。請想num[i]的含義，我們求i結尾的，只要把i-1結尾的最大加上i就好了，當然如果i-1結尾最大子數組是負的，i結尾最大子數組就是它本身。
為什么O(N)？時間省在哪里了？我們省掉了許多沒必要的計算，計算i時，之前的數組和已經都計算過，樸素算法并沒有記錄下來，而是重復計算，造成時間浪費。算法優化的過程就是去掉重復計算的過程。
?
1-2
fun1:時間O(log10,N)，空間O(1)
FUN2:時間O(log10,N)，空間O(log10,N)
第一個函數只是有限幾個變量，所以空間O(1),一個循環n每次縮小十倍，時間O(log10,N).
第二個函數遞歸調用，這個函數沒執行完就跳到另外的函數，會壓函數棧，空間O(log(10,n)),
而時間還是O(log10,N)，復雜度沒變但是時間稍長。
?
?
?
作業完了
?
我們說拓展：如何求二維數組的最大和子數組？
如果大家看懂了之前的講解，我給個提示：利用第二個代碼和第四個代碼思想的結合
?
?
解釋：
1? ?2? 3? ?4
-1 -2? 1? ?2
1? ?3? ?-2? 1
-1? -2? -1? -3
如圖是前三行整體最大
怎么做呢？
先用第二個代碼的思想，我們進行預處理
每個數代表這一列到這個數位置截止，累加和。
1? 2? 3? 4
0? 0? 4? 6
1? 3? 2? 7
0? 1? 1? 4
然后，我們枚舉每一列的起點和終點分別為第0，1，2，3行
然后壓縮成一維來做
比如求1-3行的這個矩形，我們拿0和3行減一下就行了
0-1，1-2，1-3，4-4=-1，-1，-2，0就是1-3行壓縮后的結果
然后按一維do來做就好
時間復雜度：n行m列：
預處理：每個元素弄一遍，O(N*M)
枚舉壓縮：起點n個終點n個，數量：O(N^2)，對于每個矩陣，我們壓縮為一維，只要減一下就好，O(M)
dp：每個一維O(M)
?
求最大子長方體或者多維也一樣，預處理，三維壓二維，二維壓一維，按一維dp來做。
?
算法優化的過程就是去除重復計算過程的過程
想象一下沒有預處理沒有dp的樸素做法時間是多少？
算法的魅力
?
以前寫過這個問題的總結了，所以這次可能寫的有點簡單。看不懂再去之前博客找找
