CS 170 作业 1
到期的 1//26//2021" , at 10:00 pm (grace period until 11:59pm) "\mathbf{1 / 2 6 / 2 0 2 1 \text { , at 10:00 pm (grace period until 11:59pm) }}
1个研究小组
列出您的学习组中成员的姓名和 SID。如果您没有合作者，请写“无”。
2 课程政策
阅读完后，将以下句子复制并在您提交的作业上签名。
“我已阅读并理解课程大纲和政策。”
3 理解学术不诚实
在回答以下任何问题之前，请确保您已仔细阅读教学大纲和课程政策 ( https://cs170.org/syllabus/ )。对于下面的每条语句，请写下 OKO K 如果课程政策允许并且不允许 OKO K 否则。
(a) 你向一位之前学过 CS 170 的朋友询问了他们的作业答案，其中一些作业与本学期的习题集重叠。您查看他们的解决方案，然后用自己的话写下来。
(b) 您同一天有 5 次期中考试，并且作业落后。你决定向已经完成作业的同学寻求帮助。他们告诉你如何做前三个问题。
© 您在线查找作业问题并找到准确的解决方案。然后你用自己的话写下来并引用来源。
(d) 你在互联网上查找 Dijkstra 的问题，并遇到了一个与你作业中的问题非常相似的网站。你阅读它，包括解决方案，然后关闭网站，写下你的解决方案，并在作业中引用网站 URL。
4 渐近复杂度比较
(a) 对以下函数进行排序，以便对于所有 i,ji, j ， 如果 f_(i)f_{i} 出现在之前 f_(j)f_{j} 然后按顺序 f_(i)=O(f_(j))f_{i}=O\left(f_{j}\right) 。不要证明你的答案合理。
- f_(1)(n)=3^(n)f_{1}(n)=3^{n}
- f_(2)(n)=n^((1)/(3))f_{2}(n)=n^{\frac{1}{3}}
- f_(3)(n)=12f_{3}(n)=12
- f_(4)(n)=2^(log_(2)n)f_{4}(n)=2^{\log _{2} n}
- f_(5)(n)=sqrtnf_{5}(n)=\sqrt{n}
- f_(6)(n)=2^(n)f_{6}(n)=2^{n}
- f_(7)(n)=log_(2)nf_{7}(n)=\log _{2} n
- f_(8)(n)=2^(sqrtn)f_{8}(n)=2^{\sqrt{n}}
- f_(9)(n)=n^(3)f_{9}(n)=n^{3}
作为答案，您可以将函数写为列表，例如 f_(8),f_(9),f_(1),dotsf_{8}, f_{9}, f_{1}, \ldots
(b) 在下列每一项中，请指出是否 f=O(g),f=Omega(g)f=O(g), f=\Omega(g) ，或两者（在这种情况下 f=Theta(g)f=\Theta(g) ）。简要证明你的每个答案的合理性。回想一下，就渐近增长率而言，对数 < 多项式 < 指数。
|
f(n)f(n) |
g(n)g(n) |
| （我） |
log_(3)n\log _{3} n |
log_(4)(n)\log _{4}(n) |
| (二) |
n log(n^(4))n \log \left(n^{4}\right) |
n^(2)log(n^(3))n^{2} \log \left(n^{3}\right) |
| (三) |
sqrtn\sqrt{n} |
(log n)^(3)(\log n)^{3} |
| （四） |
n+log nn+\log n |
n+(log n)^(2)n+(\log n)^{2} |
f(n) g(n)
(i) log_(3)n log_(4)(n)
(ii) n log(n^(4)) n^(2)log(n^(3))
(iii) sqrtn (log n)^(3)
(iv) n+log n n+(log n)^(2)| | $f(n)$ | $g(n)$ |
| :--- | :---: | :---: |
| (i) | $\log _{3} n$ | $\log _{4}(n)$ |
| (ii) | $n \log \left(n^{4}\right)$ | $n^{2} \log \left(n^{3}\right)$ |
| (iii) | $\sqrt{n}$ | $(\log n)^{3}$ |
| (iv) | $n+\log n$ | $n+(\log n)^{2}$ |
5 计算阶乘
考虑计算问题 N!=1xx2xx cdots xx NN!=1 \times 2 \times \cdots \times N 。
（一个） NN 是 log N\log N 位长（这是需要多少位来存储大小为 N)N) 。找到一个 f(N)f(N) 以便 N!N! 是 Theta(f(N))\Theta(f(N)) ) 位长。尽可能简化你的答案，并论证为什么它是正确的。
注意：您不能使用斯特林公式。
(b) 给出一个简单（朴素）的算法来计算 NN ！.您可以假设将两个位相乘（例如 0xx0,0xx10 \times 0,0 \times 1 ) 需要 1 个时间单位。
请给出算法描述和运行时分析。
6 多项式计算
给定系数 a_(0),dots,a_(n)inNa_{0}, \ldots, a_{n} \in \mathbb{N} ，考虑多项式：p(x)=sum_(k=0)^(n)a_(k)x^(k)p(x)=\sum_{k=0}^{n} a_{k} x^{k}
对于这个问题，假设两个自然数的加法和乘法只需要 O(1)\mathcal{O}(1) 时间（无论它们有多大）。
(a) 描述一个简单的算法，给定 [a_(0),dots,a_(n)]\left[a_{0}, \ldots, a_{n}\right] 和 xx ，计算 p(x)p(x) 。分析其运行时间与多项式次数的关系 nn 。
(b) 作为替代方案，我们可以计算以下表达式：p(x)=a_(0)+x(a_(1)+x(a_(2)+dots+x(a_(n-1)+x*a_(n))dots))p(x)=a_{0}+x\left(a_{1}+x\left(a_{2}+\ldots+x\left(a_{n-1}+x \cdot a_{n}\right) \ldots\right)\right)
描述并分析使用上述表达式计算多项式的算法。运行时间应该是一个函数 nn 以及。
按照作业指南中的描述给出由 3 部分组成的解决方案。