break语句的时间复杂度是多少？附数组查找额外元素代码分析

1. break语句本身的时间复杂度 #

break是C++中的流程控制跳转语句，作用是立即退出当前所在的循环/switch结构，单次执行仅完成一次寄存器跳转操作，耗时为固定常量，单个break语句的时间复杂度为O(1)。

2. 结合给定场景的代码整体时间复杂度分析 #

两个数组内容基本一致，仅第一个数组的中间位置额外添加了一个元素，其中数组b长度为n，数组a长度为n+1。

对应实现代码如下：

class Solution{
  public:
    int findExtra(int a[], int b[], int n) {
        // add code here.
        int index=0,flag=0;
        for (int i=0;i<n;i++){
            if(a[i]-b[i]!=0){
                index=i;
                flag=1;
                break;
            }
        }
        if(flag==0) return n;
        else return index;
    }
};

这段代码的核心逻辑是顺序遍历两个数组的对应位置，找到第一个元素不一致的索引就触发break退出循环，整体时间复杂度由循环执行的次数决定：

• 最好情况：额外元素插入在数组a的第0位，第一次循环比对就触发break，整体时间复杂度为O(1)
• 最坏情况：额外元素是数组a的最后一位（即a的前n个元素和b完全一致），循环会执行满n次后退出，整体时间复杂度为O(n)
• 题目给定场景为额外元素插入在数组中间，平均需要遍历n/2次，时间复杂度量级依然为O(n)

内容的提问来源于stack exchange，提问作者Lovlesh Baghel