&& 运算符的 C++ 代码时间复杂度

Question

我有以下两个代码：

int i=0;
while(i<=1000000000 && i!=-1) {
    i++;        
}

我认为运行时间复杂度是40亿

while条件是3次操作(i<=1000000000),(i!=-1) and &&, 和

int i=0;
    while(i!=-1) {
        if(i>=1000000000) break;
        i++;        
    }

我认为运行的时间复杂度是 30 亿，在 while 条件中是 1 个操作 (i<=1000000000) 在 if 中是 1 个操作 (i!=-1), 但是当我运行这两个代码有相同的运行ning 时间，那是为什么？

我已经将这两个代码稍微更改如下：

int n = 1000000000;
int i=0;
while(i<=n && i!=-1) {
    i++;        
}

int n = 1000000000;
int i=0;
while(i!=-1) {
if(i>=n) break;
    i++;        
}

这次 2.6s 中的第 3 个代码块运行，第 4 个是 3.1s，为什么会这样？四个代码的时间复杂度是多少？

我使用 dev-c++ IDE.

Answer 1

时间复杂度和实际运行时间是两个截然不同的东西。

只有当我们谈论可变输入大小时，时间复杂度才有意义。它说明了算法对更大输入的扩展程度。如果我们假设您的输入是 n（或前两种情况下的 1000000000），那么您所有的示例都具有线性时间复杂度。这意味着，粗略地说，如果 n 大两倍，运行时间也会加倍。

实际运行时间在某种程度上取决于复杂性，但您无法可靠地计算它。原因是：编译器优化、CPU 优化、OS 线程管理和许多其他。

我认为 'time complexity' 是指计算机要执行的原始操作数。那么就没有区别了

while(i<=1000000000 && i!=-1)

和

while(i!=-1) {
    if(i>=1000000000) break;

因为 最有可能 运算符 && 不是作为 'take first operand, take second operand, and perform some operation on them' 实现的，而是作为一系列条件跳转：

    if not FirstCondition then goto FalseBranch
    if not SecondCondition then goto FalseBranch
TrueBranch:
    ... here is your loop body
FalseBranch:
    ... here is the code after loop

这正是您在第二个示例中手工完成的操作。但是，这些东西仅对特定的编译器和优化设置有意义（在发布版本中，您的循环将被任何后代编译器完全消除）。

&& 运算符的 C++ 代码时间复杂度

c++ code time complexity of && operator

c++

time-complexity