什么是算法？它有什么特点?
算法是一组规则或过程，用于解决特定问题或完成特定任务。算法通常包括一系列的步骤和操作，可以将输入数据转换为输出数据。算法可以应用于各种领域，如计算机科学、数学、工程等，用于解决计算、优化、搜索、排序、加密等问题。
算法有以下几个特点：
精确性：算法必须准确无误地描述每一个步骤和操作，以便实现正确的结果。
确定性：算法必须是确定性的，即对于相同的输入数据，算法的输出结果应该是唯一的。
可行性：算法必须能够在有限的时间和空间内完成计算任务。
有限性：算法必须在有限的时间内终止，并给出结果，不能无限循环或死循环。
通用性：算法必须适用于一般情况，而不是特定的输入数据或问题。
算法分析题
(1) 假设某算法的输入规模为\(n\)时计算时间为 \(3\times 2^n\) 在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机其运行速度为第一台的\(64\)倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？
有64倍的算力，又有 \(2^6=64\)，则在\(t\)秒内，可以处理规模为\(n+6\)的方案。
(2) 若上述算法的计算时间改进为 \(T(n) = n^2\) 其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题？
设可以解决规模为\(m\)的问题
则有 \(3\times 2^n = m^2\)，得 \(m = \sqrt{3*2^n}\)
则可以解决规模为m的问题
(3) 若上述算法的计算时间改进为 \(T(n)= 8\) 其余条件不变，则在新机器上用\(t\)秒时间能解输入规模为多大的问题？
能够解决任意大规模的问题
利用求极限的方法（洛必达法则）分析下列函数对的渐进关系，并用渐进符号 \(\Theta\), \(\Omega\), \(O\) 表示：
(1)\(f(n) = \sqrt[3]{n} + 5\log{n}; \ g(n) = \sqrt[5]{n}\log{n} + 390\)
\[\lim_{n\rightarrow\infty}\dfrac{f(n)}{g(n)} =\lim_{n\rightarrow\infty} \dfrac{\sqrt[3]{n} + 5 \log n}{\sqrt[5]{n} \log n +390}\\ =\lim_{n\rightarrow\infty} \dfrac{n^{-\frac{2}{3}} + \frac{5}{n}}{n^{-\frac{4}{5}} \log n + n^{-\frac{4}{5}}} = \lim_{n\rightarrow\infty} \dfrac{(n^{-\frac{2}{3}} + n^{-1})\times n^{\frac{4}{5}}}{\log n + 1} \\ = \lim_{n\rightarrow\infty} \dfrac {n^{-\frac{1}{5}} + n^{\frac{2}{15}}}{log n + 1} > \lim_{n\rightarrow\infty}\dfrac {n^{\frac{1}{15}}}{log n + 1} \\ = \lim_{n\rightarrow\infty}\dfrac{\frac{1}{15}n^{\frac{1}{15}}n^{-1}}{\frac{1}{n}}=\lim_{n\rightarrow\infty}\dfrac{n^\frac{1}{15}}{15} =+\infty \]所以\(f(n) = \Omega(g(n))\)
(2)\(f(n) = 20n^2 + 20n + n\log{n}; \ g(n) = 100n^{1.9} + 1000\)
\[\lim_{n\rightarrow\infty}\dfrac{f(n)}{g(n)} = \dfrac{20n^2 + 20n + n\log{n}}{100n^{1.9} + 1000} > \dfrac{20n^2}{100n^{1.9}+1000} \\ =\lim_{n\rightarrow\infty} \dfrac{40n}{190n^{0.9}} = \frac{4}{19}n^{0.1} = +\infty \]所以\(f(n) = \Omega(g(n))\)
(3)\(f(n) = n(\log(\log{n}))^{10}; \ g(n) = n(\log{n})^2 + 1.8n\)
\[\lim_{n\rightarrow\infty}\dfrac{f(n)}{g(n)} =\dfrac{n(\log(\log{n}))^{10}}{n(\log{n})^2 + 1.8n} =\dfrac{(\log(\log n))^{10}}{(\log n)^2+1.8} \\ 令m=\log n ，则有\lim_{n\rightarrow\infty}\dfrac{f(n)}{g(n)}= \lim_{m\rightarrow\infty}\dfrac{f(m)}{g(m)} =\dfrac{(\log m)^{10}}{m^2+1.8} \\ 令k=\log m ，则有\lim_{m\rightarrow\infty}\dfrac{f(m)}{g(m)} = \lim_{k\rightarrow\infty}\dfrac{f(k)}{g(k)} =\dfrac{k^{10}}{e^{2k}+1.8} < \dfrac{k^{10}}{e^k} \\ =\lim_{k\rightarrow\infty}\dfrac{f(k)}{g(k)}=10\dfrac{k^9}{e^k}=10\times 9 \dfrac{k^8}{e^k} = \dots =\dfrac{10!}{e^k} =0 \]所以\(f(n) = O(g(n))\)
(4) \(f(n) = 145n^4 + 20n + n\log{n}; \ g(n) = \frac{1}{n}(1.01)^n + 1.8n + 505\)
\[\lim_{n\rightarrow\infty}\dfrac{f(n)}{g(n)} = \dfrac{145n^5+20n^2+n^2\log n}{(1.01)^n + 1.8n^2 + 505n} < \dfrac{145n^5+20n^2 + n^2 \log n}{(1.01)^n} \\ = 0 \]所以\(f(n) = O(g(n))\)
利用复杂度渐进阶的定义证明下列性质：
1，\(O(f) + O(g) = O(f + g)\)
首先，我们可以将\(O(f)\)和\(O(g)\)中的常数和低阶项去掉，因为它们对于渐进复杂度没有影响。因此，我们可以写出：
\(O(f) + O(g) = k_1 \cdot f(n) + k_2 \cdot g(n)\)
其中\(k_1\)和\(k_2\)是两个常数。现在我们需要分析\(k_1 \cdot f(n) + k_2 \cdot g(n)\)的复杂度。
根据大O符号的定义，我们可以得出：
\(k_1 \cdot f(n) + k_2 \cdot g(n) \leq (k_1 + k_2) \cdot max(f(n), g(n))\)
因此，我们可以得出：
\(O(f) + O(g) = k_1 \cdot f(n) + k_2 \cdot g(n) = O(max(f(n), g(n))) = O(f + g)\)
2，\(O(f)O(g) = O(fg)\)
由于\(O(f(n))\)和\(O(g(n))\)分别表示\(f(n)\)和\(g(n)\)的上界，因此我们可以将它们表示为：
\(O(f(n)) \leq c_1 f(n)\)，其中\(c_1\)是一个正常数 \(O(g(n)) \leq c_2 g(n)\)，其中\(c_2\)是一个正常数
将这两个不等式相乘，我们得到：
\(O(f(n))O(g(n)) \leq c_1c_2f(n)g(n)\)
这说明\(O(f(n))O(g(n))\)是\(O(f(n)g(n))\)的上界。因此，我们可以得出：
\(O(f(n))O(g(n)) = O(f(n)g(n))\)
3，如果 \(g(n) = O(f(n))\), 则 \(O(g(n)) + O(f(n)) = O(f(n))\)
如果\(g(n) = O(f(n))\)，那么存在一个常数\(c>0\)和\(n_0 > 0\)，使得对于所有\(n \geq n_0\)，有\(g(n) \leq cf(n)\)。
根据\(O\)符号的加法规则，\(O(g(n)) + O(f(n)) = O(max(g(n), f(n)))\)。
因此，我们需要证明\(O(max(g(n), f(n))) = O(f(n))\)。
根据\(g(n) = O(f(n))\)的定义，我们有\(g(n) \leq cf(n)\)。因此，\(max(g(n), f(n)) = f(n) + (g(n) - f(n)) \leq f(n) + cf(n) = (c+1)f(n)\)。
4，\(O(Cf(n)) = O(f(n))\), 其中 \(C\) 是任意正常数
假设存在一个函数\(h(n) = Cf(n)\)，我们要证明\(h(n) = O(f(n))\)。
根据大O符号的定义，我们需要找到一个正常数\(C_1\)和一个正整数\(N_1\)，使得对所有n > N_1，有\(Cf(n) \leq C_1 \cdot f(n)\)。
我们可以选取\(C_1 = C\)，此时我们得到\(Cf(n) \leq C \cdot f(n)\)。这个条件对所有n都成立，所以我们可以取\(N_1 = 1\)。
现在我们已经找到了正常数\(C_1\)和正整数\(N_1\)，使得对所有n > N_1，有\(Cf(n) \leq C_1 \cdot f(n)\)。因此，我们可以得出\(h(n) = Cf(n) = O(f(n))\)。
5，如果 \(f = O(g)\), 那么 \(g = \Omega(f)\)
如果\(f = O(g)\)，那么我们可以得出\(g = \Omega(f)\)，因为f(n)的增长速度被g(n)所限制，同时g(n)的增长速度至少是f(n)。换句话说，当f(n)是O(g(n))时，我们可以得出g(n)是函数f(n)的一个渐进下界。
6，如果 \(f = O(g)\), \(g = O(f)\), 那么 \(f = \Theta(g)\)
根据大Θ符号的定义，如果存在两个正常数\(C_1\)和\(C_2\)以及一个正整数\(N\)，使得对所有\(n > N\)，有\(C_1 \cdot g(n) \leq f(n) \leq C_2 \cdot g(n)\)，那么我们可以说\(f = \Theta(g)\)。
由于\(f = O(g)\)和\(g = O(f)\)，我们可以找到一个整数\(N = \max(N_1, N_2)\)，使得当\(n > N\)时，\(C_1 \cdot g(n) \leq f(n)\)以及\(C_2 \cdot f(n) \geq g(n)\)。这意味着我们已经满足了大Θ符号的条件。因此，我们可以得出结论：\(f = \Theta(g)\)。
7，如果 \(f = O(g)\), \(f = \Omega(g)\), 那么 \(f = \Theta(g)\)
- 如果\(f = O(g)\)，那么根据大O符号的定义，存在一个正常数\(C_1\)和一个正整数\(N_1\)，使得对所有\(n > N_1\)，有\(f(n) \leq C_1 \cdot g(n)\)。这意味着函数f(n)的增长速度被函数\(C_1 \cdot g(n)\)所限制，即f(n)在渐进意义上小于等于g(n)。
- 如果\(f = \Omega(g)\)，那么根据大Ω符号的定义，存在一个正常数\(C_2\)和一个正整数\(N_2\)，使得对所有\(n > N_2\)，有\(f(n) \geq C_2 \cdot g(n)\)。这意味着函数f(n)的增长速度至少是函数\(C_2 \cdot g(n)\)，即f(n)在渐进意义上大于等于g(n)。
现在我们知道\(f = O(g)\)且\(f = \Omega(g)\)，所以我们可以说\(f(n)\)和\(g(n)\)在渐进意义上是相互约束的。换句话说，f(n)和g(n)在渐进意义上既不快于也不慢于彼此。
5，一般有三种估计算法时间复杂度函数的方法：迭代次数估计(循环体的循环次数)、基本操作次数估计(在差一个常数倍数情况下出现频度最高的基本运算)、递归函数法(用递归函数来表达时间复杂度函数)。请用上述方法估计下列算法的时间复杂度函数的渐近阶。
Algorithm A Count
\(Input\) \(A\) \(positive\) \(integer\) \(n\)
\(Output\) \(count\) \(=\) \(number\) \(of\) \(times\) \(that\) \(step\) \(5\) \(is\) \(executed\)
\(\quad count\) \(\gets\) \(0\)
\(\quad for\) \(i\) \(\gets\) \(1\) \(to\) \(n\)
\(\quad \quad m\) \(\gets\) \(\left\lfloor{\frac{n}{i}}\right\rfloor\)
\(\quad \quad for\) \(j\) \(\gets\) \(1\) \(to\) \(m\)
\(\quad \quad \quad count\) \(\gets\) \(count\) \(+\) \(1\)
\(\quad \quad endfor\)
\(\quad endfor\)
\(return\) \(count\)
请统计迭代次数作为时间复杂度, 并估计渐近阶。
经过统计，得到了迭代次数\(T(n)=\sum\limits_{i=1}^{n} \lfloor \frac{n}{i} \rfloor\)
则有\(T(n)≤ n\sum\limits_{i=1}^{n} \frac{1}{i} ≤ n\log(n-1)\)
又有\(\lfloor \frac{n}{i}\rfloor>\frac{n}{i} - 1\)
则有\(T(n)≥-n + n\sum\limits_{i=1}^n \frac{1}{i}≥-n + n \log(n-1)\)
则有\(T(n) = O(n\log n)\)
Algorithm B ModifyInsertionSort
\(Input\) \(An\) \(array\) \(of\) \(A[1..n]\) \(of\) \(n\) \(elements\)
\(Output\) \(A[1..n]\) \(sorted\) \(in\) \(nondecreasing\) \(order\)
\(\quad for\) \(i\) \(\gets\) \(2\) \(to\) \(n\)
\(\quad \quad x\) \(\gets\) \(A[i]\)
\(\quad \quad k\) \(\gets\) \(ModifyBinarySearch\) \((A\left[1..i\right], x)\)
\(\quad \quad for\) \(j\) \(\gets\) \(i-1\) \(downto\) \(k\)
\(\quad \quad \quad A[j+1]\) \(\gets\) \(A[j]\)
\(\quad \quad endfor\)
\(\quad \quad A[k]\) \(\gets\) \(x\)
\(\quad endfor\)
其中\(ModifyBinarySearch(A\left[1..i\right],x)\)是改进的二分查找函数，无论x是否在\(A\left[1..i\right]\)中，它返回\(A\left[1..i\right]\)中比x小的元素个数加1。
请分别用\(ModifyBinarySearch(A\left[1..i\right],x)\)中的比较运算和语句5中的赋值运算作为基本运算统计算法的时间复杂度，并给出渐近阶。你认为哪个渐近阶是正确的？
假设序列A中，每个元素的值都相等。
则有k一直等于1。
则迭代次数\(T(n) = \sum\limits_{i=1}^{n} \log i + i\)
求完渐进得到\(T(n) = O(n^2)\)
标签：infty,frac,log,cdot,dfrac,第一章,算法,Assignment,quad From： https://www.cnblogs.com/alphainf/p/17274208.html