当使用break语句时，如何计算时间复杂度

Question

void F ( int a[], int n ) { // args: array a[ ] of size n
   for ( int k = n/2; k>0; k/=2 ) {
     for ( int j = 0; j< n; j++ ) {
       if ( a[j] >= a[k] ) break;
       else { int m = a[j]; a[j] = a[k]; a[k] = m; }
}}}

现在，第一个for循环是2+ log base-2 of n (2 +2循环)。就是这样。

第二个(嵌套的)循环是一个问题。如果这是最好/最坏的情况，那么解决方案分别是常量和线性的。但是考虑到如果语句成功是有时间的，那么嵌套循环的复杂度是多少？

到目前为止，我尝试的是2+ (n/2)(2 + 1) + (n/2)(2 + 3) =2+ 4n

其中2是初始化和比较，(n/2)(2 + 1)是if语句成功的时间，(n/2)(2 + 3)是用于else语句的。

但我认为这是完全错误的。我想我遗漏的是break语句简单地结束了循环，一切都变得混乱了。它应该是n/2吗

Answer 1

你可以做的就是找出你的算法进入if和else语句的概率。然后，你可以通过将它们相加，根据它们被执行的机会来加权，从而对复杂性进行平均。然后你得到的是平均复杂度(显然不要与最坏情况下的复杂度混淆)。

Average =p*O(if语句)+ (1 - p) *O(ELSE语句)，其中p是if语句执行的概率，0 => p >= 1。

编辑: Witn probability在这里我不是在暗示随机性，你可以把它看作是定义if和else语句中调用之间的比率的一种方式，并且你可以从if语句中的谓词中推导出这个比率。