---
title: Algorithm Homework III
description: 中央大學演算法分組作業3 (II)
---
# [查看題目](https://drive.google.com/file/d/1vS89wICfNHYsA5IyxSnuL1qAwlnhjXSF/view)
# Problem 1(solved)
- [x] 完成[name=Zongyou]
- [x] 審查[name=ZoneTwelve]
## Topic:
Given a **sorted** array A[1...n] of ndistinct integers, you want to find out the index ifor which A[i] = iif it exists. Please design a **Divide-and-Conquer** algorithm that runs in time **O(lgn)**. (Analyze your algorithm and show it is correct.)(要寫Code)
## Solution 1:
```C++=
#include <iostream>
#include <vector>
using namespace std;
void solution(vector<int> seq){
int l = 0, r = seq.size() - 1, mid = (l + r)/2;
while(l < r){
if(seq[mid] == mid){
cout << mid << endl;
return;
}
if(mid < seq[mid])
r = mid - 1;
else
l = mid + 1;
mid = (l + r)/2;
}
if(l == seq[l])
cout << l << endl;
else
cout << "No" << endl;
}
int main(){
int n;
vector<int> seq;
while(cin >> n)
seq.push_back(n);
solution(seq);
}
```
---
# Problem 2(solved)
- [x] 完成 [name=悠哉小方]
- [x] 審核 [name=Joe]
## Topic
Analyze **best-case**, **average-case**, and **worst-case** performance of the following pseudocode which describes a sorting algorithm.
Append your analyzing process or reasons.
```pseudocode=
i = 2
while i <= size
if i == 1 or array[i] >= array[i - 1]
i += 1
else
swap array[i], array[i - 1]
i -= 1
```
## Solution 1:
$T(n)=T(n-1)+f(n)$
### Best case:
原本已經就從小排到大，這時$f(n)=1$，因為每次都只要跟前一項做比較，不需swap
T(n)=T(n-1)+1
T(n-1)=T(n-2)+1
...
T(2)=T(1)+1
+)T(1)=0
T(n)=n-1 -> O(n)
### Worst case:
原本是從大排到小，這時$f(n)=2*n-1$，因為要跟前面每一項做交換，並在跑到下一項需要2*n-1
T(n)=T(n-1)+2n-1
T(n-1)=T(n-2)+2(n-1)-1
...
T(2)=T(1)+2\*2-1
+)T(1)=0
T(n)=2(2+3+...+n)-(n-1)=(n-1)(n+2)-(n-1)=n^2-1 -> O(n^2)
### Average case:
> 我覺得這裡可以討論一下 [name=Zongyou][color=#b936ea]
>>淳方的方法有疑慮的地方在於f(n)的計算是基於worst case的狀況下,也就是前n - 1項都小於第n項
>
>> 我的想法是從base case開始,考慮一個排序過的序列多加一個數的狀況,就像selection sort, 舉例來說
> f(n) = $\dfrac{1}{n}$(0 + 1 + .. + n - 1)
> T(1) = 0
> T(2) = T(1) + $\dfrac{1}{2}$(0 + 1)
> T(3) = T(2) + $\dfrac{1}{3}$(0 + 1 + 2)
> ...
> T(n) = T(n - 1) + $\dfrac{1}{n}$(0 + 1 + ... + n - 1)
> 其中,因為第n個數在排序後可能出現在n個位置,所以每個位置的可能性為$\dfrac{1}{n}$, 而後面的級數則是每個位置搬移次數的總和
> >>他的$f(n)$應該是把比較的時間也算進去了[name=Joe][color=#bd203b]
> >>我發現好像是我把f(n)跟T(n)搞混了XD,抱歉[name=Zongyou]
平均下來$f(n)=(1+3+...+2n-1)/n=n$
T(n)=T(n-1)+n
T(n-1)=T(n-2)+(n-1)
...
T(2)=T(1)+2
+)T(1)=0
T(n)=(n+2)(n-1)/2 -> O(n^2)
---
# Problem 3(solved)
- [x] From Slader
- [x] 完成[name=Zongyou]
- [x] 審查[name=ZoneTwelve]
## Topic
Indicate, for each pair of expressions (A, B) in the table below, whether A is **O, o, Ω, ω,** or **Θ**‚ of B. Assume that k >= 1, epsilon > 0, and c > 1 are constants. Your answer
should be in the form of the table with “yes” or “no” written in each box.
## Solution 1:
| A | B | O | o | Ω | ω | Θ |
| --------------| -------------------- | --- | --- | --- | --- | --- |
| $\\lg^kn$ | $\\n^c$ | O | O | X | X | X |
| $\\n^k$ | $\\c^n$ | O | O | X | X | X |
| $\sqrt{n}$ | $\\n^{sin\ n}$ | X | X | X | X | X |
| $\\2^n$ | $\\2^{n/2}$ | X | X | O | O | X |
| $\\n^{lg\ c}$ | $\\c^{lg\ n}$ | O | X | O | X | O |
| $\\lg(n!)$ | $\\lg(n^n)$ | O | X | O | X | O |
---
# Problem 4(還沒審查)
- [x] 完成[name=Zongyou]
- [ ] 審查
## Topic
Given two non-negative function f, g (i.e. f, g : N → R * ) such that f≠O(g), f≠θ (g), and f≠Ω(g).
## Solution
let f(n) = $e^{-n}$ and g(n) = sin(n) + 1
=> f(n) -> 0 as n -> ∞ and g(n) 會在 0 與 2 之間震盪
所以f≠O(g), f≠θ (g), and f≠Ω(g)
# Problem 5
- [ ] 完成
- [ ] From [CLRS Solution](https://walkccc.github.io/CLRS/Chap03/Problems/3-3/)
## Topic:
### a. topic
Rank the following functions by order of growth; that is, find an arrangement g1, g2, .., g30 of the functions g1 = **Ω**(g2), g2 = **Ω**(g3), ..., g29 = **Ω**(g30).Partiotion your list into equivalence classes such that functions f(n)and g(n) are in the same calss if and only if f(n) = **Θ**(g(n))
| | | | | | |
| --- | --- | --- | --- | --- | ---- |
| $\\lg(lg^∗n)$ | $2^{lg^∗\ n}$ | $(\sqrt{2})^{lg\ n}$ | $n^2$ | $\\n!$ |$\\(lg\ n)!$|
| $\\(\dfrac{3}{2})^n$ | $\\n^3$ | $\\lg^2n$ | $\\lg(n!)$ | $\\2^{2^n}$ | $\\n^{1/lg\ n}$ |
| $\\lg\ lg\ n$ | $\\lg^*n$ | $\\n\cdot2^n$ | $\\n^{lg\ lg\ n}$ | $\\lg\ n$ | $\\1$ |
| $\\2^{lg\ n}$ | $\\(lg\ n)^{lg\ n}$ | $\\e^n$ | $\\4^{lg\ n}$ | $\\(n+1)!$ | $\\\sqrt{lg\ n}$|
| $\\lg^*(lg\ n)$ | $\\2^\sqrt{2\ lg\ n}$ | $\\n$ | $\\2^n$ | $\\n\ lg\ n$| $\\2^{2^{n+1}}$ |
- [x] 建立內容 [name=ZoneTwelve]
- [x] [color=red]<span style="color:red">建議</span>複查內容 [name=Joe]
>給我連結
>我打[name=ZoneTwelve][color=#0084ff]
>> https://walkccc.github.io/CLRS/Chap03/Problems/3-3/
>> 我菜雞我道歉[name=Joe][color=#bd302b]
> LOL[name=ZoneTwelve][color=#0084ff]
### b. topic
Give an example of a single nonnegative function *f*(n) such that for all functions g<sub>*i*</sub>(n) in part (a), *f*(n) is neither O(g<sub>*i*</sub>(n)) nor Ω(g<sub>*i*</sub>(n)).
## Solution :
### a. Solution
\begin{split}
2^{2^{n+1}}\\
﹀\\
2^{2^{n}}\\
﹀\\
(n+1)!\\
﹀\\
n!\\
﹀\\
e^n\\
﹀\\
n \cdot 2^n\\
﹀\\
2^n\\
﹀\\
\dfrac{3}{2}^n
﹀\\
(lg\ n)^{lg\ n} &= n^{lg\ lg \ n}\\
﹀\\
(lg\ n)!\\
﹀\\
n^3\\
﹀\\
n^2 &= 4^{lg\ n}\\
﹀\\
nlg\ n\ \ and\ \ lg(n!)\\
﹀\\
n &= 2^{lg\ n}\\
﹀\\
(\sqrt{2})^{lg\ n}(&= \sqrt{n})\\
﹀\\
2^{\sqrt{2\ lg\ n}}\\
﹀\\
lg^2n\\
﹀\\
ln\ n\\
﹀\\
\sqrt{lg\ n}\\
﹀\\
\sqrt{lg\ n}\\
﹀\\
ln\ ln\ n\\
﹀\\
2^{lg^*n}\\
﹀\\
lg^*n\ \ and\ \ lg^*(lg\ n)\\
﹀\\
lg(lg^*n)\\
﹀\\
n^{\dfrac{1}{lg\ n}}(&= 2)\ \ and\ \ 1\\
\end{split}
>這是a的答案[name=Joe][color=#bd302b]
>> Thx[name=ZoneTwelve][color=#0084ff]
> 我簡直數學式 Generator [name=ZoneTwelve][color=#0084ff]
>
### b. solution
找出一個比 $2^{2^{n+1}}$大且震盪的函數
\begin{split}
\left\{{
2^{2^{n+2}}, if\ n\ is\ even\\
0, if\ n\ is\ odd
\\}
\right .
\end{split}
> 啥 Array [name=ZoneTwelve][color=#0084ff]
>> 沒事我看你打出來了[name=Joe][color=#bd302b]
>>> OK [name=ZoneTwelve][color=#0084ff]
---
# Problem 6
- [x] 完成
## Topic and solution
1.
>Let f(n) and g(n) be asymptotically positive functions.
>Prove or disprove each of the following conjectures.
>a. f = O(g) implies g = O(f)
>> let $f(n) = n, g(n) = n^2$
>> then $f = O(g)$, but $g$ != $O(f)$
>b.$f + g = Θ(min(f + g))$
>> let $f(n) = n, g(n) = n^2$
>> => $n + n^2$ != Θ(min(f + g)) = Θ(n)
>>
>c.f = O(g) => lg(f) = O(lg(g)), where lg(g) >= 1 and f >= 1 for all sufficiently large n
>>f = O(g) => exist c > 0, n0 s.t. 0 <= f <= cg
>>∵lg(g) >= 1 and f >= 1
>>∴0 <= lg(f) <= lg(cg) <= c'lg(g)
>>=> lg(f) = O(lg(g))
>d.f = O(g) => $2^f$ = O($2^g$)
>>let f = 2n, g = n
>>=> 2n = O(n), but $2^{2n}$ != O($2^n$)
>e.f = O($f^2$)
>>let f(n) = $2^{-n}$, then $f^2(n)$ = 2^{-2n}
>>where $\dfrac{f(n)}{f^2(n)}$ = ∞ as n -> ∞
>>=> f != O($f^2$)
>f.f = O(g) => g = Ω(f)
>>f = O(g) => exist c > 0, n0 s.t. 0 <= f <= cg
>>=> 0 <= f/c <= g
>>=> g = Ω(f)
>g.f(n) = Θ(f(n/2))
>>let f(n) = $2^{2n}$ => f(n/2) = $2^n$
>>and $2^{2n}$ != $2^n$
>h.f + o(f) = Θ(f)
>>let g = o(f) => for all c > 0, exist n0, g < cf, when n > n0
>>to prove exist c1, c2 > 0 s.t. c1f <= f + g <= c2f
>>∵f < f + g < 2f
>>=> take c1 = 1, c2 = 2, and it's done
2.
>f(n) = Θ(g(n)) => f(n)/g(n) -> c != 0 as n -> ∞
>>let f(n) = 0
>>=>0 = O(1), but 0/1 = 0
---
# Problem 7
- [ ] 完成
>報告時有討論的整理一下貼上來[name=zongyou][color=#b936ea]
>> 誰要貼
>> [name=ZoneTwelve][color=#0084ff]
Sign in with Wallet
Connect another wallet