哪个"for"循环的时间复杂度更高？

Question

    int i;
    for(i=0;i<n;i++)
    {
     if(i==number);
       break;
    }

或

    for(i=0; ;i++)
    {
    if(i==number)
    break;
    }

删除 for 循环中的比较部分是否会影响时间复杂度？

Answer 1

你不能准确地说哪个更快......

第一个的时间复杂度O(min(n, number))，第二个是O(number) 。

---

如果 n 大于（或等于）数字，则第一个将等于第二个。

• 第一：O(number)（因为数字小于n，min(n, number) = number
• 第二：O(number)

---

如果 n 小于数字，则第一个将更快（因为它也停止在 n 中）。

• 第一：O(n)（因为 n 小于数字，min(n, number) = n
• 第二：O(number)

---

从整体上看，第一个会更快。

如您所见，删除 for 外观中的比较确实会有所不同，考虑到它们的复杂性变得不同的第二种情况，这是很明显的。