算法分析与设计-算法分析题-第1章-题目答案与解析_求下列函数的渐近表达式并比较复杂度大小

第1章 算法概述 算法分析题 题目+答案解析

算法分析题

笔记参考：
算法设计与分析-笔记-第1章-算法概述

1-1 求下列函数的渐近表达式

(1)$3n^2+10n$

$\because \mathrm{O}(n)<\mathrm{O}(n^2)$

$\because 3n^2+10n=\mathrm{O}(n^2)$

(2)$\frac{n^2}{10}+2^n$

$\because \mathrm{O}(n^2)<\mathrm{O}(2^n)$

$\therefore \frac{n^2}{10}+2^n=\mathrm{O}(2^n)$

(3)$21+\frac{1}{n}$

$\because \mathrm{O}(\frac{1}{n})<\mathrm{O}(1)$

$\therefore 21+\frac{1}{n}=\mathrm{O}(1)$

(3)$log{n}^3$

$\because log{n}^3=3logn$

$\therefore log{n}^3=\mathrm{O}(logn)$

(4)$10log{3}^n$

$\because 10log{3}^n=10nlog3$

$\therefore 10log{3}^n=\mathrm{O}(n)$

1-2 $\mathrm{O}(2)与\mathrm{O}(2)的区别$

$\mathrm{O}(1)=\mathrm{O}(2)$，可以表示同一个函数，但其常数因子不同

1-3 按渐近阶从低到高排列：$4n^2,logn,3^n,20n,2,n^{\frac{2}{3}},n!$

$2,logn,n^{\frac{2}{3}},20n,4n^2,3^n,n!$

1-4 某算法在输入规模为$n$时的计算时间为$T(n)$。在某计算机上实现并完成该算法的时间为$t$秒，那在运行速度为该计算机的64倍的计算机上用同一算法在$t$秒内能解决多大规模的问题？

设能解决$n1$规模的问题

（1）$T(n)=3\times 2^n$

$\because t=3\times 2^n=\frac{3\times 2^{n}1}{64}$

$\therefore n1=n+6$

（2）$T(n)=n^2$

$\because t=n^2=\frac{n{1}^2}{64}$

$\therefore n1=8n$

（3）$T(n)=8$

计算时间与问题规模无关，可以解决任意规模的问题

1-5计算机XYZ的运行速度是计算机ABC的100倍，对于复杂度为$n,n^2,n^3和n!$的算法，若用计算机XYZ在1小时能解决输入规模为$n$的问题，那么用计算机ABC能在1小时解决多大规模的问题？

设能解决$n1$规模的问题

$n1=100n\Rightarrow n1=100n$

$n{1}^2=100n^2\Rightarrow n1=10n$

$n{1}^3=100n^3\Rightarrow n1=\sqrt[3]{100}n=4.64n$

$n1!=100n!\Rightarrow n1<n+log100=n+6.64$

$\because (Stiringling公式)n!\approx \sqrt{2\pi n}(\frac{n}{e}{)}^n$

∴ n 1 ! = 100 n ! l o g n 1 ! = l o g n ! + l o g 100 l o g 2 π n 1 ( n 1 e ) n 1 = l o g 2 π n ( n e ) n + l o g 100 n 1 l o g 2 π n 1 ( n 1 e ) = n l o g 2 π n ( n e ) + l o g 100 n 1 l o g 2 π n 1 ( n 1 e ) < n l o g 2 π n 1 ( n 1 e ) + l o g 100 n 1 < n + l o g 100 = n + 6.64

$$\begin{aligned} \therefore n1!&=100n!\\ logn1!&=logn!+log100\\log\sqrt{2\pi n1}(\frac{n1}{e})^{n1}&=log\sqrt{2\pi n}(\frac{n}{e})^{n}+log100\\n1log\sqrt{2\pi n1}(\frac{n1}{e})&=nlog\sqrt{2\pi n}(\frac{n}{e})+log100\\n1log\sqrt{2\pi n1}(\frac{n1}{e})&<nlog\sqrt{2\pi n1}(\frac{n1}{e})+log100\\n1&<n+log100=n+6.64 \end{aligned}$$ ∴n1!logn1!log2πn1 ​(en1​)n1n1log2πn1 ​(en1​)n1log2πn1 ​(en1​)n1​=100n!=logn!+log100=log2πn ​(en​)n+log100=nlog2πn ​(en​)+log100<nlog2πn1 ​(en1​)+log100<n+log100=n+6.64​

1-6对下列各组函数$f(n)$和$g(n)$，确定$f(n)=\mathrm{O}(g(n))$或$f(n)=\Omega (g(n))$或$f(n)\Theta (g(n))$

(1)$f(n)=log{n}^2,g(n)=logn+5$

$\because f(n)=2logn,当n\to \infty 时，logn=logn$

$\therefore f(n)=\Theta (g(n))$

(2)$f(n)=log{n}^2,g(n)=\sqrt{n}$

$\because f(n)=2logn,当n\to \infty 时，logn<\sqrt{n}$

$\therefore f(n)=\mathrm{O}(g(n))$

(3)$f(n)=n,g(n)=lo{g}^{2}n$

$\because 当n\to \infty 时，\sqrt{n}>logn即n>log{2}^n$

$\therefore f(n)=\Omega (g(n))$

(4)$f(n)=nlogn+n,g(n)=logn$

$\because 当n\to \infty 时，nlogn>logn$

$\therefore f(n)=\Omega (g(n))$

(5)$f(n)=10,g(n)=log10$

$\because 1=1$

$\therefore f(n)=\Theta (g(n))$

(6)$f(n)=lo{g}^{2}n,g(n)=logn$

$当n\to \infty 时，lo{g}^{2}n>logn$

$\therefore f(n)=\Omega (g(n))$

(7)$f(n)=2^n,g(n)=100n^2$

$\because 当n\to \infty 时，2^n>n^2$

$\therefore f(n)=\Omega (g(n))$

(8)$f(n)=2^n,g(n)=3^n$

$\because 当n\to \infty 时，2^n<3^n$

$\therefore f(n)=\mathrm{O}(g(n))$

1-7 证明：$n!=o(n^n)$

$\because (Stiringling公式)n!\approx \sqrt{2\pi n}(\frac{n}{e}{)}^n$

$\therefore \underset{n\to \infty }{\lim }\frac{n!}{n^n}=\frac{\sqrt{2\pi n}}{e^n}=0即n!=o(n^n)$

1-8 3n+1问题：下面的算法用于确定n的初始值，试分析该算法片段所需计算时间的上界和下界

while (n > 1)
    if (odd(n))
        n = 3 * n + 1;
	else
        n = n / 2;
1
2
3
4
5

上诉代码的意思是：当$n$为奇数时，$n=3\ast n+1$，当$n$为偶数时，$n=n/2$，直到$n=1$，那么最快跳出循环的情况是$n$为为2的幂次的情况，即所需时间的下界为$\Omega (logn)$，无法计算上界。

1-9证明：如果一个算法在平均情况下的计算时间复杂度为$\Theta (f(n))$，则该算法在最坏情况下所需的计算时间为$\Omega (f(n))$

$\because T_{avg}(N)\le T_{max}(N)$

$\therefore T_{max}=\Omega (T_{avg}(N))=\Omega (\Theta (f(n)))=\Omega (f(n))$