两算法输出一致但耗时近翻倍：时间复杂度及差异原因问询

先直接给结论：两个算法的时间复杂度完全相同，都是O(n)，但实际运行耗时的差距来自于I/O操作的模式和C++标准库的默认行为，而非算法本身的复杂度。

先把两个算法的代码贴出来方便对照：

1st Algorithm #

for (int i =0 ;i<n;i++){
    cin>>p[i];
    if(i>0){
        if(p[i-1]>p[i]){
            cout<<p[i]<<" ";
        } else{
            cout<<"-1"<<" ";
        }
    }
}

2nd Algorithm #

for (int i =0 ;i<n;i++){
    cin>>p[i];
}
for (int i =0 ; i<n-1;i++){
    if(p[i]>p[i+1]){
        cout<<p[i]<<" ";
    } else{
        cout<<"-1"<<" ";
    }
}

1. 时间复杂度分析 #

两个算法的核心操作都是：

• 读取n个输入（线性次数，O(n)）
• 执行n-1次判断和输出（同样是线性次数，O(n)）

没有嵌套循环、递归或者其他高于线性阶的操作，所以两者的时间复杂度都是线性时间O(n)。

2. 实际耗时差异的核心原因 #

虽然时间复杂度一致，但I/O操作的执行模式差异拉满了实际耗时：

• cin与cout的默认同步机制：C++标准库默认把cin和cout绑定同步（等价于调用std::ios_base::sync_with_stdio(true)），这意味着每次执行cin前，都会自动刷新cout的缓冲区。第一个算法是「读一个元素，立即输出一次判断结果」的交替模式，cin和cout频繁切换，导致大量的缓冲区刷新操作——每次从用户态切换到内核态处理I/O都有固定开销，多次累加后总耗时自然翻倍。

• I/O的批量处理优势：第二个算法采用「批量读入 → 批量输出」的模式，先一次性把所有输入读完，再集中处理输出。这种模式下，cout能更高效地利用缓冲区：输出内容会先积累在用户态缓冲区，直到缓冲区满或者程序结束时才一次性写入内核，大幅减少了内核态切换的次数，整体I/O开销低很多。

举个直观的例子：如果n是10000，第一个算法会触发近10000次cin+cout的交替，每次cin都要刷新cout；而第二个算法只有10000次集中的cin，再10000次集中的cout，缓冲区刷新的次数会少一大截。

验证小技巧 #

要是在第一个算法开头加上两行代码关闭同步：

ios::sync_with_stdio(false);
cin.tie(nullptr);

你会发现它的耗时会大幅降低，接近第二个算法的水平——这就实锤了同步机制是耗时差异的核心原因。

内容的提问来源于stack exchange，提问作者aatish uniyal