# NYU CS-UY 1134 Lab3

AI悦创原创python 1v1NYUNYU – Tandon School of Engineering大约 8 分钟...约 2322 字

## # Vitamins (30 minutes)

For big-O proof, show that there exists constants c, and $n_0$ such that $f(n) ≤ c*g(n)$ for every $n ≥ n_0$, then $f(n) = O(g(n))$.

For big-Θ proof, show that there exists constants $c_1$, $c_2$, and $n_0$ such that $c1*g(n) ≤ f(n) ≤ c2*g(n)$ for every $n ≥ n_0$, then $f(n) = Θ(g(n))$.

1. Use the **formal proof of big-O and big-**Θ in order to show the following (10 minutes):

a) $𝑛^2 + 5𝑛 − 2$ is $𝑂(𝑛^2)$

b) $\frac{n^2-1}{n+1}$ is $O(n)$

C) $\sqrt{5n^2 - 3n + 2}$

1. State True or False and explain why for the following (10 minutes):

a) $8n^2(\sqrt{n})$ is $O(n^3)$

b) $8𝑛^2(\sqrt{𝑛})$ is $Θ(𝑛^3)$

1. Sort the following 18 functions in an increasing asymptotic order and $write < or <= between$ each two subsequent functions to indicate if the first is asymptotically less than or asymptotically equivalent to the second function respectively.

For example, if you were to sort:

$𝑓_1(𝑛) = 𝑛$, $𝑓_2(𝑛) = 𝑙𝑜𝑔(𝑛)$, $𝑓_3(𝑛) = 3𝑛$, $𝑓_4(𝑛) = 𝑛^2$,

your answer could be $𝑙𝑜𝑔(𝑛) < ( 𝑛 <= 3𝑛) < 𝑛^2$

Hint: Try grouping the functions like so: linear, quadratic, cubic, exponential ... etc

$𝑓_1(𝑛) = 𝑛$

$𝑓_2(𝑛) = 500𝑛$

$𝑓_3(𝑛) = \sqrt{𝑛}$

$𝑓_4(𝑛) = 𝑙𝑜𝑔(\sqrt{𝑛})$

$𝑓_5(𝑛) = \sqrt{𝑙𝑜𝑔(𝑛)}$

$𝑓_6(𝑛) = 1$

$𝑓_7(𝑛) = 3^𝑛$

$𝑓_8(𝑛) = 𝑛 · 𝑙𝑜𝑔(𝑛)$

$𝑓_9(𝑛) = \frac{n}{log(n)}$

$𝑓_{10}(𝑛) = 700$

$𝑓_{11}(𝑛) = 𝑙𝑜𝑔(𝑛)$

$𝑓_{12}(𝑛) = \sqrt{9n}$

$𝑓_{13}(𝑛) = 2^𝑛$

$𝑓_{14}(𝑛) = 𝑛^2$

$𝑓_{15}(𝑛) = n^3$

$𝑓_{16}(𝑛) = \frac{n}{3}$

$𝑓_{17}(𝑛) = \sqrt{n^3}$

$𝑓_{18}(𝑛) = 𝑛!$

zh

1. 常数时间：$f_6(n) = 1$$f_{10}(n) = 700$。在这两个之间，$f_6(n)$ 明显比 $f_{10}(n)$ 小。
2. 对数时间：$f_{11}(n) = log(n)$$f_4(n) = log(\sqrt{n})$。我们知道 $log(\sqrt{n}) = 0.5 \times log(n)$，所以 $f_4$ 是较小的。
3. 次线性时间：$f_5(n) = \sqrt{log(n)}$
4. 线性时间中的一些函数：$f_1(n) = n$, $f_2(n) = 500n$, 和 $f_{16}(n) = \frac{n}{3}$
5. 几个其他线性和次线性时间的函数：$f_3(n) = \sqrt{n}$, $f_{12}(n) = \sqrt{9n}$$f_{12}$ 可以简化为 $3\sqrt{n}$，所以 $f_3(n)$ 是较小的。
6. 线性对数时间：$f_8(n) = n \cdot log(n)$
7. 次线性时间中的一个函数：$f_9(n) = \frac{n}{log(n)}$
8. 平方时间：$f_{14}(n) = n^2$
9. 立方和次立方时间：$f_{15}(n) = n^3$$f_{17}(n) = \sqrt{n^3}$$f_{17}$ 可以简化为 $n^{1.5}$，所以 $f_{17}(n)$ 是较小的。
10. 指数时间：$f_{13}(n) = 2^n$$f_7(n) = 3^n$$f_{13}(n)$ 是较小的。
11. 阶乘时间：$f_{18}(n) = n!$ 是所有函数中增长最快的。

$f_6(n) <= f_{10}(n) < f_4(n) <= f_{11}(n) < f_5(n) < f_{16}(n) <= f_1(n) <= f_2(n) < f_3(n) <= f_{12}(n) < f_8(n) < f_9(n) < f_{14}(n) < f_{17}(n) < f_{15}(n) < f_{13}(n) < f_7(n) < f_{18}(n)$

1. 常数函数：显然，对于足够大的n，任何常数函数都比对数、线性、多项式、指数函数小：

• $𝑓_6(𝑛) = 1$
• $𝑓_{10}(𝑛) = 700$
2. 对数函数：当n增大时，对数函数的增长率低于线性函数，但高于常数函数。其中，$𝑙𝑜𝑔(\sqrt{𝑛})$实质上是$\frac{1}{2}𝑙𝑜𝑔(𝑛)$，因此增长更慢：

• $𝑓_4(𝑛) = 𝑙𝑜𝑔(\sqrt{𝑛}) = \frac{1}{2} log(n)$
• $𝑓_{11}(𝑛) = 𝑙𝑜𝑔(𝑛)$

同时，$\sqrt{𝑙𝑜𝑔(𝑛)}$随着n的增长而增长，但速度慢于直接的log(n)：

• $𝑓_5(𝑛) = \sqrt{𝑙𝑜𝑔(𝑛)}$
3. 线性函数：这些函数与n成正比。显然，$𝑛$$500𝑛$的增长速度比$\frac{n}{3}$要快：

• $𝑓_{16}(𝑛) = \frac{n}{3}$
• $𝑓_1(𝑛) = 𝑛$
• $𝑓_2(𝑛) = 500𝑛$
4. 线性对数函数$𝑛 · 𝑙𝑜𝑔(𝑛)$，它的增长速度介于线性和多项式之间：

• $𝑓_8(𝑛) = 𝑛 · 𝑙𝑜𝑔(𝑛)$
5. 分数线性函数：随着n的增长，分母$log(n)$增加，使得整体函数的增长减慢，但它仍然比纯线性函数增长得快：

• $𝑓_9(𝑛) = \frac{n}{log(n)}$
6. 平方根函数：这类函数的增长比线性慢，但比对数快：

• $𝑓_3(𝑛) = \sqrt{𝑛}$
• $𝑓_{12}(𝑛) = \sqrt{9n} = 3\sqrt{n}$
7. 平方函数：明显比线性和平方根函数增长得快：

• $𝑓_{14}(𝑛) = 𝑛^2$
8. 立方根和立方函数

• $𝑓_{17}(𝑛) = \sqrt{n^3} = n^\frac{2}{3}$，它的增长比$n^2$慢，但比$n$快。
• $𝑓_{15}(𝑛) = n^3$，显然，它的增长速度是所有多项式函数中最快的。
9. 指数函数：显然，$3^𝑛$的增长速度比$2^𝑛$快，它们都明显比多项式函数快：

• $𝑓_{13}(𝑛) = 2^𝑛$
• $𝑓_7(𝑛) = 3^𝑛$
10. 阶乘函数：增长最快。

• $𝑓_{18}(𝑛) = 𝑛!$

$𝑓_6(𝑛) \leq 𝑓_{10}(𝑛) \leq 𝑓_4(𝑛) \leq 𝑓_{11}(𝑛) \leq 𝑓_5(𝑛) \leq 𝑓_{16}(𝑛) \leq 𝑓_1(𝑛) \leq 𝑓_2(𝑛) \leq 𝑓_3(𝑛) \leq 𝑓_{12}(𝑛) \leq 𝑓_9(𝑛) \leq 𝑓_8(𝑛) \leq 𝑓_{14}(𝑛) \leq 𝑓_{17}(𝑛) \leq 𝑓_{15}(𝑛) \leq 𝑓_{13}(𝑛) \leq 𝑓_7(𝑛) \leq 𝑓_{18}(𝑛)$

1. Given the generator function, write the output: (10 minutes)

## # 知识补充

1. 大O和大Θ 的区别是什么？

1. 大O符号（O）: 描述算法的上界。当我们说一个算法的时间复杂度是 (O(f(n))) 时，我们意味着在最坏的情况下，该算法的执行时间会按 (f(n)) 的速率增长（或更慢）。简言之，(O(f(n))) 提供了算法性能的一个上限。

例如，如果一个算法的时间复杂度为 (O(n^2))，那么我们可以认为在最坏的情况下，该算法的执行时间不会比 (n^2) 快速增长。

2. 大Θ符号（Θ）: 描述算法的上界和下界，并且这两个界限是相同的。当我们说一个算法的时间复杂度是 (\Theta(f(n))) 时，我们意味着在最坏的情况下，该算法的执行时间按 (f(n)) 的速率增长，而在最好的情况下，它也是 (f(n))。也就是说，(\Theta(f(n))) 描述了算法性能的确切增长率。

例如，如果一个算法的时间复杂度为 (\Theta(n^2))，这意味着无论是最好的情况还是最坏的情况，该算法的执行时间都会按 (n^2) 的速率增长。

### # 1. 线性查找

• 最坏情况：目标值在数组的最后一个位置或根本不存在。此时，你需要检查整个数组，所以时间复杂度是 (O(n))。
• 最好情况：目标值就在数组的第一个位置。时间复杂度是 (O(1))。
• 平均情况：时间复杂度是 (O(n))。

### # 2. 二分查找

• 最坏情况：需要检查整个数组，直到只剩一个元素。时间复杂度是 (O(\log n))。
• 最好情况：目标值恰好在数组中间。时间复杂度是 (O(1))。
• 平均情况：时间复杂度是 (O(\log n))。

### # 3. 冒泡排序

• 最坏情况：当数组是完全逆序的时候，时间复杂度是 (O(n^2))。
• 最好情况：当数组已经是排序好的，只需遍历一次数组以确认，时间复杂度是 (O(n))。
• 平均情况：时间复杂度是 (O(n^2))。

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

• 0
• 0
• 0
• 0
• 0
• 0

• 按正序
• 按倒序
• 按热度