前言：最近快到FDS考试了，po重刷了一下学校的题目，自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦，所以在此共享一下我的题目和自己写的解题思路，欢迎各位指出错误~全章节预计会陆续更新，可在专栏查看~
HW1
1. The major task of algorithm analysis is to analyze the time complexity and the space complexity.
T
2. The Fibonacci number sequence {FN} is defined as: F0=0, F1=1, FN=FN−1+FN−2, N=2, 3, .... The time complexity of the function which calculates F(N) recursively is Θ(N!).
F 时间复杂度应该是O(2^N)，而N!比2^N还要大。
3. O(N^2) is the same as O(1+2+3+⋯+N).
T 计算sum(1+2+...+N) = (1 + N) * N / 2，去掉常数部分之后可发现 O(1+2+..+N)也为O(N^2)
4. n^0.01 is O(logn).
F n的多少次方最后都比logn大
5. For the following piece of code
if ( A > B ){
for ( i=0; i<N*2; i++ )
for ( j=N*N; j>i; j-- )
C += A;
}
else {
for ( i=0; i<N*N/100; i++ )
for ( j=N; j>i; j-- )
for ( k=0; k<N*3; k++)
C += B;
}
the lowest upper bound of the time complexity is O(N^3).
T else的j的取值范围会卡住i的范围，如果i大于N，j根本就不会运行。所以i的范围为1~N，else部分T(N)=O(N^3)。if部分更好算，也是O(N^3)。（常数部分都可以直接忽略）
6.Given the following four algorithms with their runtimes for problem size 100 and their time complexities:
| Algorithm |
Runtime |
Time Complexity |
| A |
100 |
O(N) |
| B |
50 |
O(N2) |
| C |
25 |
O(N3) |
| D |
10 |
O(N4) |
Which algorithm is the fastest for problem size 200?
D 把O(N)变成O(2N)代入计算，那么对于A来说runtime翻2倍，对于B来说翻2*2=4倍，C翻8，D翻16..可得100*2,50*4,25*8,10*16，160最小，所以选D
7.Let n be a non-negative integer representing the size of input. The time complexity of the following piece of code is:
x = 0;
while ( n >= (x+1)*(x+1) )
x = x+1;
A.O(logn)
B.O(n1/2)
C.O(n)
D.O(n2)
B x=1,2,3,...一直算到根号n，while循环停止
8.The recurrent equations for the time complexities of programs P1 and P2 are:
P1: T(1)=1,T(N)=T(N/3)+1
P2: T(1)=1,T(N)=3T(N/3)+1
Then the correct conclusion about their time complexities is:
A.they are both O(logN)
B.O(logN) for P1, O(N) for P2
C.they are both O(N)
D.O(logN) for P1, O(NlogN) for P2
B 递推即可
9.Which of the following pairs of functions has the same speed of growth:
A.2N and NN
B.N and 2/N
C.N2logN and NlogN2
D.NlogN2 and NlogN
D
10.To judge an integer N (>10) is prime or not, we need to check if it is divisible by any odd number from 3 to N. The time complexity of this algorithm is __.
A.O(N/2)
B.O(根号(N))
C.O(根号(N)logN)
D.O(0.5logN)
B 质数的判断至少要试因子到根号N
11.The Fibonacci number sequence {FN} is defined as: F0=0, F1=1, FN=FN−1+FN−2, N=2, 3, .... The space complexity of the function which calculates FNrecursively is:
A.O(logN)
B.O(N)
C.O(FN)
D.O(N!)文章来源：https://www.toymoban.com/news/detail-838812.html
B 注意：空间是可以释放后重新使用的，而时间是不可以重新利用第二次的。所以斐波那契数列会先从F（N）->F（N-1）->F（N-2）层层递归做到F（1），然后返回N层（N是深度）。返回之后空间已经被释放，在下次递归时又可以用上次用过的空间。所以空间复杂度为递归深度N。文章来源地址https://www.toymoban.com/news/detail-838812.html
到了这里，关于数据结构英文习题解析-第一章 算法复杂度分析Algorithm Analysis的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
