时间复杂性问题-yiteyi-C++库

以下函数fun（）的时间复杂度是多少？假设log（x）返回以2为基数的log值。

null

C++

                         void                                     fun()                       
                         {                       
                                                 int                                     i, j;                       
                                                 for                                     (i = 1; i <= n; i++)                       
                                                 for                                     (j = 1; j <=                                     log                                     (i); j++)                       
                                                 cout <<                                     "GeeksforGeeks"                                     ;                       
                         }                       
           
                         // This code is contributed by SHUBHAMSINGH10.                       

C

                         void                                     fun()                       
                         {                       
                                                 int                                     i, j;                       
                                                 for                                     (i = 1; i <= n; i++)                       
                                                 for                                     (j = 1; j <=                                     log                                     (i); j++)                       
                                                 printf                                     (                                     "GeeksforGeeks"                                     );                       
                         }                       

JAVA

                         static                                     void                                     fun()                       
                         {                       
                                                 int                                     i, j;                       
                                                 for                                     (i =                                     1                                     ; i <= n; i++)                       
                                                 for                                     (j =                                     1                                     ; j <= log(i); j++)                       
                                                 System.out.printf(                                     "GeeksforGeeks"                                     );                       
                         }                       
           
                         // This code is contributed by umadevi9616                       

Python3

                         import                                     math                       
                         def                                     fun():                       
                                                 i                                     =                                     0                       
                                                 j                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 for                                     j                                     in                                     range                                     (                                     1                                     ,math.log(i)                                     +                                     1                                     ):                       
                                                 print                                     (                                     "GeeksforGeeks"                                     )                       
           
                         # This code is contributed by SHUBHAMSINGH10.                       

C#

                         static                                     void                                     fun()                       
                         {                       
                                                 int                                     i, j;                       
                                                 for                                     (i = 1; i <= n; i++)                       
                                                 for                                     (j = 1; j <= log(i); j++)                       
                                                 Console.Write(                                     "GeeksforGeeks"                                     );                       
                         }                       
           
                         // This code is contributed by umadevi9616                       

Javascript

                         const fun()                       
                         {                       
                                                 let i, j;                       
                                                 for                                     (i = 1; i <= n; i++)                       
                                                 for                                     (j = 1; j <= Math.log(i); j++)                       
                                                 document.write(                                     "GeeksforGeeks"                                     );                       
                         }                       
           
                         // This code is contributed by SHUBHAMSINGH10.                       

上述函数的时间复杂度可以写成θ（log1）+θ（log2）+θ（log3）+θ（logn），也就是θ（logn！）对数n的增长顺序对于n的大值来说，‘n logn’是相同的，即θ（logn！）=θ（n对数n）。所以fun（）的时间复杂度是θ（n logn）。表达式θ（logn！）=θ（n logn）可以很容易地从以下公式推导出来斯特林近似（或斯特林公式） .

log n! = n*log n - n = O(n*log(n))

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。资料来源： http://en.wikipedia.org/wiki/Stirling%27s_approximation

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

THE END

技术文章