java - 从代码中逐行计算 while 和 switch case 的时间复杂度以及插入排序的示例

Question

有许多指南可以告诉您如何通过查看代码/算法并逐行应用来计算时间复杂度。但是我发现 while 和 switch 循环很难。有人可以帮我弄清楚在这种情况下该怎么做吗？

插入排序的示例以及我是如何卡住的:

int i,j,n=a.length,temp; //c1
        for(i=1;i<n;i++) // (n)
        {
            j=i-1; // c2
            temp=a[i]; // c3
            while(j>=0&&a[j]>temp) (Stuck here)
            {
                a[j+1]=a[j];// c4
                j=j-1; //c5
            }
            a[j+1]=temp; //c6
        }

Answer 1

由于您不只是浏览集合，而是在某些时候根据某些条件打破循环，您的结果将有一个最好和一个最坏 案例场景。

外层 for 循环将始终执行 n - 1迭代。在计算复杂度常量时通常会省略，因此您的外循环将具有常量复杂度 n。 .

while 循环将取决于两个条件:j大于 0 并且 j大于 temp .

应该a[j] > temp为每个 n 持有，那么您的代码的复杂度应为 n .

如果另一方面，a[j] < temp对于每个 n , 然后 j>=0将是决定性条件。 j将从小开始增加为 n增加，因此两个循环都将运行 nj次。

自 n < nj ，然后，您可以得出结论，最佳情况的时间复杂度为 n .另一方面，最坏的情况是nj。 .自 j = n - 1 , 你可以说复杂度是 n(n - 1)这将导致 n^2 - n ，这将大致导致最坏情况下的时间复杂度为 n^2 .