我的作业涉及大O分析，我认为我已经掌握了窍门，但我不能100%确定。你们这些可爱的人会介意看一眼，告诉我我是否走上了正轨吗？
作业如下。对于问题1和问题3，我的分析和答案在//标记之后的右边。对于问题2，我的分析和答案在算法类型下面。
提前感谢您的帮助！：-）
1.For each of the following program fragments, give a Big-Oh analysis of the running time in terms of N:
(a) // Fragment (a)
for ( int i = 0, Sum = 0; i < N; i++ ) // N operations
for( int j = 0; j < N; j++ ) // N operations
Sum++; // Total: N^2 operations => O(N^2)
(b) // Fragment (b)
for( int i = 0, Sum = 0; i < N * N; i++ ) // N^2 operations
for( int j = 0; j < N; j ++ ) // N operations
Sum++; // Total: N^3 operations => O(N^3)
(c) // Fragment (c)
for( int i = 0, Sum = 0; i < N; i++ ) // N operations
for( int j = 0; j < i; j ++ ) // N-1 operations
Sum++; // Total: N(N-1) = N^2 – N operations => O(N^2)
(d) // Fragment (d)
for( int i = 0, Sum = 0; i < N; i++ ) // N operations
for( int j = 0; j < N * N; j++ ) // N^2 operations
for( int k = 0; k < j; k++ ) // N^2 operations
Sum++; // Total: N^5 operations => O(N^5)
2. An algorithm takes 0.5 milliseconds for input size 100. How long will it take for input size 500 if the running time is:
a. Linear
0.5 *5 = 2.5 milliseconds
b. O( N log N)
O (N log N) – treat the first N as a constant, so O (N log N) = O (log N)
Input size 100 = (log 100) + 1 = 2 + 1 = 3 operations
Input size 500 = (log 500) + 1= 2.7 + 1 = 3.7 ≈ 4 operations
Input size 100 runs in 0.5 milliseconds, so input size 500 takes 0.5 * (4/3) ≈ 0.67 milliseconds
c. Quadratic
Input size 100 in quadratic runs 100^2 operations = 10,000 operations
Input size 500 in quadratic runs 500^2 operations = 250,000 operations = 25 times as many
Input size of 100 runs in 0.5 milliseconds, so input size of 500 takes 25 * 0.5 = 12.5 milliseconds
d. Cubic
Input size 100 in quadratic runs 100^3 operations = 1,000,000 operations
Input size 500 in quadratic runs 500^3 operations = 125,000,000 operations = 125 times as many
Input size of 100 runs in 0.5 milliseconds, so input size of 500 takes 125 * 0.5 = 62.5 milliseconds
3. Find the Big-O for the following:
(a) f(x) = 2x^3 + x^2 log x // O(x^3)
(b) f(x) = (x^4 – 34x^3 + x^2 -20) // O(x^4)
(c) f(x) = x^3 – 1/log(x) // O(x^3)
4. Order the following functions by growth rate: (1 is slowest growth rate; 11 is fastest growth rate)
__6_ (a) N
__5_ (b) √N
__7_ (c) N^1.5
__9_ (d) N^2
__4_ (e) N log N
__2_ (f) 2/N
_11_ (g) 2^N
__3_ (h) 37
_10_ (i) N^3
__1_ (j) 1/ N^2
__8_ (k) N^2 /log N
* My logic in putting (j) and (f) as the slowest is that as N grows, 1/N^2 and 2/N decrease, so their growth rates are negative and therefore slower than the rest which have positive growth rates (or a 0 growth rate in the case of 37 (h)). Is that correct?
我看了你的问题1到3，看起来不错。
遵循以下规则并自行检查：
1） 乘法常数可以省略，示例50n^2简化为n^2
2） 如果a>b，n^a支配n^b示例n^3支配n^2，因此n^3+n^2+n简化为n3
3） 任何指数支配任何多项式示例3^n主导n^5示例2^n主导n^2+5n+100
4） 任何多项式支配任何对数示例n占主导地位（log n）3
关于问题4，请使用以下内容作为指南（从最小到最大）：
Log2n<n<n log2n<n^2<n^3<2^n
时间计算的（b）的答案是错误的。你不能假定n中的一个是常数。因此nlogn变为1log1，这意味着log1为0。所以0。
所以答案是100 log100运算，而500 log500。。。
从最小到最大。b是4，a是5。c、 e、k是位置6以及位置7和位置8的竞争。你给出的1,2,3的位置是正确的。9,10,11的位置是准确的。
我会检查6、7、8的一些分析，让你知道。。
如果你需要对我的回答进行澄清，你可以对此发表评论。。
@op你能告诉我你为什么考虑O（nlgn）=O（lg n）吗？据我所知，你对Q2第b部分的分析实际上是对O（lg n）算法的分析，要分析nlgn算法，你需要考虑左边的n。
-
（a） 正确
（b） 正确
（c） 正确。0+1+2+…+（n-1）=n（n-1）/2=0.5n^2-0.5n=O（n^2）
（d） 正确（像（c）一样有1/2，但复杂性仍然是O（N^5）） -
a。正确
b.设K为一个步骤的持续时间
K*（100 log 100）=0.5，因此K=7.5*10^-4
K*（500对数500）=7.5*1-^-4*500对数500=3.3737ms或者，（500 log 500）/（100 log 100）=6.7474
当n=500时，它将慢6.7474倍，6.7474*0.5ms=3.3737msc。正确
d.正确的 -
（a） 正确
（b） 正确
（c） 纠正 -
__5_（a）N
__4_（b）√N
__7_（c）N^1.5
__9_（d）N^2
__6_（e）N log N
__2_（f）2/N
_11_（g）2^N
__3_（h）37
_10_（i）N^3
__1_（j）1/N^2
__8_（k）N^2/log N
我同意（f）和（j）的定位。然而，你应该意识到，它们不会出现在"野外"，因为每个算法都至少有一个步骤，因此无法击败O（1）。请参阅是否存在O（1/n）算法？以获得更详细的解释。