比Big-Oh時，把summation展開，然後所有項目換成最後一項的和項，因為0到n都是正數(計算的都是程式的執行次數，所以沒有負數)，所以換完一定會大於等於原來的summation。
Question
成大109資工 時間複雜度題目 1
Question
Please derive the corresponding time complexity (Big-Oh) for each of the following five program segments.
exercise
k=0;
for(i=0;i<N; i++)
k++;
ans
\(
\displaystyle\sum_{i=0}^{N-1}1
=\overbrace{1+1+\dots+1}^{N\text{ terms}}
\)
\(
=N=O(N)
\)
exercise
k=0;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
k++;
ans
\(
\displaystyle\sum_{i=0}^{N-1}
\displaystyle\sum_{j=0}^{N-1}
1
=\displaystyle\sum_{i=0}^{N-1}(\overbrace{1+1+\dots+1}^{N\text{ terms}})
=\displaystyle\sum_{i=0}^{N-1}N
\)
\(
=(\overbrace{N+N+\dots+N}^{N\text{ terms}})
=N\cdot N=N^2=O(N^2)
\)
exercise
k=0;
for(i=0;i<N;i++)
for(j=0;j<i;j++)
k++;
ans
\(
\displaystyle\sum_{i=0}^{N-1}
\displaystyle\sum_{j=0}^{i-1}
1
=
\displaystyle\sum_{i=0}^{N-1}
(\overbrace{1+1+\dots+1}^{i\text{ terms}})
=
\displaystyle\sum_{i=0}^{N-1}i
\)
\(
=
0+1+2+\dots+(N-1)
\leq
(\overbrace{(N-1)+(N-1)+\dots+(N-1)}^{N\text{ terms}})
=N(N-1)
\)
\(
=N^2-N=O(N^2)
\)
exercise
k=0;
for(i=0;i<N;i++)
for(j=0;j<i*i;j++)
for(z=0;z<j;z++)
k++;
ans
\(
\displaystyle\sum_{i=0}^{N-1}
\displaystyle\sum_{j=0}^{i^2-1}
\displaystyle\sum_{z=0}^{j-1}
1
=
\displaystyle\sum_{i=0}^{N-1}
\displaystyle\sum_{j=0}^{i^2-1}
j
\)
\(
\displaystyle\sum_{i=0}^{N-1}
(\overbrace{0+1+2+\dots+(i^2-1)}^{i^2\text{ terms}})
\leq
\displaystyle\sum_{i=0}^{N-1}
(i^2-1)\times i^2
\)
\(
=
\{(0^2-1)\cdot 0^2+(1^2-1)\cdot 1^2+\dots+[(N-1)^2-1]\cdot (N-1)^2\}
\)
\(
\leq
\{\underbrace{[(N-1)^2-1]\cdot (N-1)^2+[(N-1)^2-1]\cdot (N-1)^2+\dots+[(N-1)^2-1]\cdot (N-1)^2}_{N\text{ terms}}\}
\)
\(
=
N[(N-1)^2-1]\cdot (N-1)^2
=O(N^5)
\)
exercise
k=0;
for(i=0;i<N;i++)
for(j=0;j<i*i;j++)
if(j%i==0)
for(z=0;z<j;z++)
k++;
ans
先看最內層z的那層，
計算k的執行次數為
\(
\displaystyle\sum_{z=0}^{j-1}1
=j
\)次
討論
if(j%i==0)
如果要z那層執行的話，
需要j為i的倍數，
則j可能為
\( 0\cdot i,\;1\cdot i,\;2\cdot i,\dots,\;(i-1)\cdot i \)
意思就是
\( j=0 \)時，k執行0次，
\( j=1\cdot i \)時, k執行\(1\cdot i\)次
\( j=2\cdot i \)時, k執行\(2\cdot i\)次
\( \vdots \)
\( j=(i-1) \cdot i\)時, k執行\((i-1) \cdot i\)次
就可得到j的for loop那層以下(意思是已經包含if和z那層了)的summation(這是k++的執行次數)為
\(
\displaystyle\sum_{h=0}^{i-1}h\cdot i
\)
接著考慮加上i那層的for loop 為
\(
\displaystyle\sum_{i=0}^{N-1}
\displaystyle\sum_{h=0}^{i-1}h\cdot i
\)
開始計算Big-Oh
\(
\displaystyle\sum_{i=0}^{N-1}
\displaystyle\sum_{h=0}^{i-1}h\cdot i
=
\displaystyle\sum_{i=0}^{N-1}
[\overbrace{0i+1i+2i\dots+(i-1)i}^{i\text{ terms}}]
\)
\(
\leq
\displaystyle\sum_{i=0}^{N-1}
[\overbrace{(i-1)i+(i-1)i+\dots+(i-1)i}^{i\text{ terms}}]
\)
\(
=
\displaystyle\sum_{i=0}^{N-1}
[(i-1)i]\cdot i
=
\displaystyle\sum_{i=0}^{N-1}
[(i^3-i^2)]
\)
\(
=
\overbrace{(0-0)+(1^3-1^2)+(2^3-2^2)+\dots+[(N-1)^3-(N-1)^2]}^{N\text{ terms}}
\)
\(
\leq
\overbrace{[(N-1)^3-(N-1)^2]+\dots+[(N-1)^3-(N-1)^2]}^{N\text{ terms}}
\)
\(
=
N[(N-1)^3-(N-1)^2]=O(N^4)
\)
Question
Let \( T(n)=\theta(f(n)) \). Derive \( f(n) \) in the simplest formula for \( T(n)=1*n+2(n-1)+\dots+(n-1)*2+n*1 \)
ans
觀察\( T(n) \)規律，
得出summation為
\(
T(n)=
\displaystyle\sum_{k=1}^{n}k\cdot(n-k+1)
\)
計算\( \Theta \):
\(
\displaystyle\sum_{k=1}^{n}kn-k^2+k
\)
(式子裡的n為常數)
\(
=
n\displaystyle\sum_{k=1}^{n}k
-
\displaystyle\sum_{k=1}^{n}k^2
+
\displaystyle\sum_{k=1}^{n}k
\)
\(
=
n\cdot\frac{n(n+1)}{2}
-
\frac{n(n+1)(2n+1)}{6}
+
\frac{n(n+1)}{2}
\)
\(
=
\frac{n^3+n^2}{2}
-
\frac{n(n+1)(2n+1)}{6}
+
\frac{n^2+n}{2}
\)
由經驗法則猜測為\( T(n)=\Theta(n^3) \)
討論\( n^3 \)係數是否為零，如果不是零，
那\( T(n)=\Theta(n^3) \)是對的。
\(
\rightarrow
\frac{n^3}{2}-\frac{2n^3}{6}
=\frac{n^3}{6}
\)
\(
\therefore
T(n)=\Theta(n^3)
\)
Question
Let \( T(n)=\Theta(f(n)) \). Derive \( f(n) \)
in the simplest formula for
\( T(n)=2^0*k+2^1*(k-1)+\dots+2^k*(k-k) \);
where \( 2^k=n \)
ans
\(
2^k=n\)
\(
\Rightarrow
\lg2^k=\lg n
\)
\(
\Rightarrow
k=\lg n
\)
代進T(n)的k:
\(
T(n)
=
2^0\cdot\lg n
+
2^1\cdot(\lg n-1)
+
\dots
+
2^{\lg n}\cdot(\lg n-\lg n)
\)
這似乎很難用最後一項去比大小。
所以另解
\(
T(n)
=
2^0\cdot\lg n
+
2^1\cdot(\lg n-1)
+
\dots
+
2^{\lg n}\cdot(\lg n-\lg n)
\)
\(
2T(n)
=
2^1\cdot\lg n
+
2^2\cdot(\lg n-1)
+
\dots
+
2^{\lg(n)+1}\cdot(\lg n-\lg n)
\)
兩式相減得
\(
2T(n)-T(n)
=T(n)
=
2^1
+
2^2
+
\dots
+
2^{\lg n}
+
2^{\lg(n)+1}\cdot(\cancelto{0}{\lg n-\lg n})
-
2^0\cdot\lg n
\)
\(
=
2^1+2^2+\dots+2^{\lg n}
-2^0\cdot \lg n
\)
|
Hint
|
\(
c\neq1,c\in R,\)
\(
a_n=ca_{n-1},\)
\(
a_1+a_2+\dots+a_n\)
\(
=a_1\frac{c^n-1}{c-1}
\)
|
|
\(
a^{\log_{a}^{x}}=x
\)
|
\(
\Rightarrow
2\frac{2^{\lg n}-1}{\cancelto{1}{2-1}}
-2^0\cdot \lg n
\)
\(
=
2\cdot(2^{\lg n}-1)
-\cancelto{1}{2^0}\cdot\lg n
\)
\(
=
2\cdot(n-1)
-\lg n
\)
\(
=\Theta(n)
\)