algorithm - 家庭作业——大O分析

Question

我的作业涉及 Big 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?

Answer 1

我查看了您的问题 1 到 3，看起来还不错。

遵循这些规则并自行检查:

1) 乘法常数可以省略，示例 50n^2 简化为 n^2

2) n^a 支配 n^b 如果 a>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，请使用以下指南(从最低到最高):

Log2 n < n < n log2 n < n^2 < n^3 < 2^n