门|门CS 2013 |问题31-yiteyi-C++库

考虑以下功能：

null

                     int                               unknown(                               int                               n) {                   
                                         int                               i, j, k = 0;                   
                                         for                               (i  = n/2; i <= n; i++)                   
                                         for                               (j = 2; j <= n; j = j * 2)                   
                                         k = k + n/2;                   
                                         return                               k;                   
                                         }                   

(A)

$Theta(n^2)$

(B)

$Theta(n^2Logn)$

(C)

$Theta(n^3)$

(D)

$Theta(n^3Logn)$

（A） A. （B） B （C） C （D） D 答复: （B） 说明： 在这里，我们必须告诉k返回的值，而不是时间复杂度。

for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;

外部循环运行n/2次内部循环运行logn次。（2^k=n=>k=logn）。现在看看内循环中k的值，n被加到k，logn次，因为内循环运行logn次。因此，总时间复杂度是内环乘以外环复杂度，即（n表示外环，nlogn表示内环）n*logn。

因此，运行内部循环一次后的k值为n^2logn。看见 http://geeksquiz.com/algorithms-analysis-of-algorithms-question-5/ 这个解决方案是由 帕鲁尔·夏尔马。

这个问题的小测验

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章