跳至主要內容

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 n0n_0 such that f(n)cg(n)f(n) ≤ c*g(n) for every nn0n ≥ n_0, then f(n)=O(g(n))f(n) = O(g(n)).

For big-Θ proof, show that there exists constants c1c_1, c2c_2, and n0n_0 such that c1g(n)f(n)c2g(n)c1*g(n) ≤ f(n) ≤ c2*g(n) for every nn0n ≥ n_0, then f(n)=Θ(g(n))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𝑛^2 + 5𝑛 − 2 is 𝑂(𝑛2)𝑂(𝑛^2)

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

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

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

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

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

  1. Sort the following 18 functions in an increasing asymptotic order and write<or<=betweenwrite < 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(𝑛)=𝑛𝑓_1(𝑛) = 𝑛, 𝑓2(𝑛)=𝑙𝑜𝑔(𝑛)𝑓_2(𝑛) = 𝑙𝑜𝑔(𝑛), 𝑓3(𝑛)=3𝑛𝑓_3(𝑛) = 3𝑛, 𝑓4(𝑛)=𝑛2𝑓_4(𝑛) = 𝑛^2,

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

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

𝑓1(𝑛)=𝑛𝑓_1(𝑛) = 𝑛

𝑓2(𝑛)=500𝑛𝑓_2(𝑛) = 500𝑛

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

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

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

𝑓6(𝑛)=1𝑓_6(𝑛) = 1

𝑓7(𝑛)=3𝑛𝑓_7(𝑛) = 3^𝑛

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

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

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

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

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

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

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

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

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

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

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

zh

首先,我们将这些函数按照它们的渐近增长率分类,然后进行排序。为了简化,我会跳过计算的细节。

以下是排序:

  1. 常数时间:f6(n)=1f_6(n) = 1f10(n)=700f_{10}(n) = 700。在这两个之间,f6(n)f_6(n) 明显比 f10(n)f_{10}(n) 小。
  2. 对数时间:f11(n)=log(n)f_{11}(n) = log(n)f4(n)=log(n)f_4(n) = log(\sqrt{n})。我们知道 log(n)=0.5×log(n)log(\sqrt{n}) = 0.5 \times log(n),所以 f4f_4 是较小的。
  3. 次线性时间:f5(n)=log(n)f_5(n) = \sqrt{log(n)}
  4. 线性时间中的一些函数:f1(n)=nf_1(n) = n, f2(n)=500nf_2(n) = 500n, 和 f16(n)=n3f_{16}(n) = \frac{n}{3}
  5. 几个其他线性和次线性时间的函数:f3(n)=nf_3(n) = \sqrt{n}, f12(n)=9nf_{12}(n) = \sqrt{9n}f12f_{12} 可以简化为 3n3\sqrt{n},所以 f3(n)f_3(n) 是较小的。
  6. 线性对数时间:f8(n)=nlog(n)f_8(n) = n \cdot log(n)
  7. 次线性时间中的一个函数:f9(n)=nlog(n)f_9(n) = \frac{n}{log(n)}
  8. 平方时间:f14(n)=n2f_{14}(n) = n^2
  9. 立方和次立方时间:f15(n)=n3f_{15}(n) = n^3f17(n)=n3f_{17}(n) = \sqrt{n^3}f17f_{17} 可以简化为 n1.5n^{1.5},所以 f17(n)f_{17}(n) 是较小的。
  10. 指数时间:f13(n)=2nf_{13}(n) = 2^nf7(n)=3nf_7(n) = 3^nf13(n)f_{13}(n) 是较小的。
  11. 阶乘时间:f18(n)=n!f_{18}(n) = n! 是所有函数中增长最快的。

所以,最终的排序为:

f6(n)<=f10(n)<f4(n)<=f11(n)<f5(n)<f16(n)<=f1(n)<=f2(n)<f3(n)<=f12(n)<f8(n)<f9(n)<f14(n)<f17(n)<f15(n)<f13(n)<f7(n)<f18(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𝑓_6(𝑛) = 1
    • 𝑓10(𝑛)=700𝑓_{10}(𝑛) = 700
  2. 对数函数:当n增大时,对数函数的增长率低于线性函数,但高于常数函数。其中,𝑙𝑜𝑔(𝑛)𝑙𝑜𝑔(\sqrt{𝑛})实质上是12𝑙𝑜𝑔(𝑛)\frac{1}{2}𝑙𝑜𝑔(𝑛),因此增长更慢:

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

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

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

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

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

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

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

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

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

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

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

整合上述分析,我们得到的排序为:
𝑓6(𝑛)𝑓10(𝑛)𝑓4(𝑛)𝑓11(𝑛)𝑓5(𝑛)𝑓16(𝑛)𝑓1(𝑛)𝑓2(𝑛)𝑓3(𝑛)𝑓12(𝑛)𝑓9(𝑛)𝑓8(𝑛)𝑓14(𝑛)𝑓17(𝑛)𝑓15(𝑛)𝑓13(𝑛)𝑓7(𝑛)𝑓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和大Θ 的区别是什么?

大O符号((O))和大Θ符号((\Theta))都是计算机科学中用于描述算法复杂性的渐近记号,但它们描述的角度和含义略有不同:

  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) 的速率增长。

简言之,大O给出了性能的上界(可能达到的最差性能),而大Θ给出了确切的性能描述,在最好和最坏情况下都符合该描述。


当然可以,我会通过几个简单的算法例子来解释这两个渐近符号。

1. 线性查找

算法:给定一个数组和一个目标值,线性查找算法会遍历整个数组,寻找是否存在目标值。

分析

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

因为最好和最坏的情况之间的时间复杂度不相同,我们不能为此算法提供一个 (\Theta) 表述。

2. 二分查找

算法:在一个有序数组中寻找目标值。每次迭代都将数组分成两半,直到找到目标值或者搜索区间为空。

分析

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

同样,由于最好和最坏情况之间的时间复杂度不相同,我们不能为此算法提供一个 (\Theta) 表述。

3. 冒泡排序

算法:通过多次遍历数组,每次都将相邻的元素进行比较并交换,直到整个数组排序完成。

分析

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

尽管最好的情况时间复杂度是 (O(n)),但通常冒泡排序被认为是一个 (O(n^2)) 的排序算法,因为在许多情况下都表现为 (O(n^2))。

希望这几个例子有助于你更好地理解渐近时间复杂度以及大O和大Θ的区别。当然,实际应用中,很多时候我们更关注最坏情况或平均情况的时间复杂度,因为这有助于我们评估算法在各种场景下的性能表现。

公众号:AI悦创【二维码】

AI悦创·编程一对一

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

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

方法一:QQopen in new window

方法二:微信:Jiabcdefh

上次编辑于:
贡献者: AndersonHJB
你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度