我们讨论过 渐近分析 , 最差、平均和最佳情况 , 渐近符号 和 回路分析 在以前的帖子中。 在这篇文章中，讨论了算法分析的实践问题。 问题1：找出以下重复出现的复杂性：
{ 3T(n-1), if n>0,T(n) = { 1, otherwise
解决方案：
Let us solve using substitution.T(n) = 3T(n-1) = 3(3T(n-2)) = 32T(n-2) = 33T(n-3) ... ... = 3nT(n-n) = 3nT(0) = 3nThis clearly shows that the complexity of this function is O(3n).
问题2：找出复发的复杂性：
{ 2T(n-1) - 1, if n>0,T(n) = { 1, otherwise
解决方案：
Let us try solving this function with substitution.T(n) = 2T(n-1) - 1 = 2(2T(n-2)-1)-1 = 22(T(n-2)) - 2 - 1 = 22(2T(n-3)-1) - 2 - 1 = 23T(n-3) - 22 - 21 - 20 ..... ..... = 2nT(n-n) - 2n-1 - 2n-2 - 2n-3 ..... 22 - 21 - 20 = 2n - 2n-1 - 2n-2 - 2n-3 ..... 22 - 21 - 20 = 2n - (2n-1) [Note: 2n-1 + 2n-2 + ...... + 20 = 2n - 1]T(n) = 1Time Complexity is O(1). Note that while the recurrence relation looks exponentialthe solution to the recurrence relation here gives a different result.
问题3：找出以下程序的复杂性：
CPP
function( int n) { if (n==1) return ; for ( int i=1; i<=n; i++) { for ( int j=1; j<=n; j++) { printf ( "*" ); break ; } } } |
解决方案： 考虑以下函数中的注释。
CPP
function( int n) { if (n==1) return ; for ( int i=1; i<=n; i++) { // Inner loop executes only one // time due to break statement. for ( int j=1; j<=n; j++) { printf ( "*" ); break ; } } } |
上述函数的时间复杂度O（n）。尽管内部循环以n为界，但由于break语句，它只执行一次。 问题4：找出以下程序的复杂性：
CPP
void function( int n) { int count = 0; for ( int i=n/2; i<=n; i++) for ( int j=1; j<=n; j = 2 * j) for ( int k=1; k<=n; k = k * 2) count++; } |
JAVA
static void function( int n) { int count = 0 ; for ( int i = n / 2 ; i <= n; i++) for ( int j = 1 ; j <= n; j = 2 * j) for ( int k = 1 ; k <= n; k = k * 2 ) count++; } // This code is contributed by rutvik_56. |
C#
static void function( int n) { int count = 0; for ( int i = n / 2; i <= n; i++) for ( int j = 1; j <= n; j = 2 * j) for ( int k = 1; k <= n; k = k * 2) count++; } // This code is contributed by pratham76. |
解决方案： 考虑以下函数中的注释。
CPP
void function( int n) { int count = 0; for ( int i=n/2; i<=n; i++) // Executes O(Log n) times for ( int j=1; j<=n; j = 2 * j) // Executes O(Log n) times for ( int k=1; k<=n; k = k * 2) count++; } |
上述函数的时间复杂度O（n log 2. n） 。 问题5：找出以下程序的复杂性：
CPP
void function( int n) { int count = 0; for ( int i=n/2; i<=n; i++) for ( int j=1; j+n/2<=n; j = j++) for ( int k=1; k<=n; k = k * 2) count++; } |
解决方案： 考虑以下函数中的注释。
CPP
void function( int n) { int count = 0; // outer loop executes n/2 times for ( int i=n/2; i<=n; i++) // middle loop executes n/2 times for ( int j=1; j+n/2<=n; j = j++) // inner loop executes logn times for ( int k=1; k<=n; k = k * 2) count++; } |
上述函数的时间复杂度O（n 2. logn）。 问题6：找出以下程序的复杂性：
CPP
void function( int n) { int i = 1, s =1; while (s <= n) { i++; s += i; printf ( "*" ); } } |
解决方案： 我们可以根据关系s来定义术语s 我 =s i-1 +i.“i”的值每迭代增加一次。包含在i处的“s”中的值 th 迭代是第一个“i”正整数的和。如果k是程序的总迭代次数，那么while循环在以下情况下终止：1+2+3..+k=[k（k+1）/2]>n所以k=O(√n） 。 上述函数的时间复杂度O(√n） 。 问题7：找到以下程序复杂性的严格上限：
CPP
void function( int n) { int count = 0; for ( int i=0; i<n; i++) for ( int j=i; j< i*i; j++) if (j%i == 0) { for ( int k=0; k<j; k++) printf ( "*" ); } } |
解决方案： 考虑以下函数中的注释。
CPP
void function( int n) { int count = 0; // executes n times for ( int i=0; i<n; i++) // executes O(n*n) times. for ( int j=i; j< i*i; j++) if (j%i == 0) { // executes j times = O(n*n) times for ( int k=0; k<j; k++) printf ( "*" ); } } |
上述函数的时间复杂度O（n 5. ).
本文由 Somesh Awasthi先生 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
