如何找到while循环的时间复杂度（Big O）？
代码1
int i = 0; int j = 0; while(i < n){ while(j < n){ printf("{%d,%d}",arr[i],arr[j]); j++; } i++; j = 0; printf("\n"); } 代码2
int result = 0; int i = 0; while (i = n / 2 && i < n){ result += arr[i]; i += 1; } } printf("%d\n", result);
我只知道如何用for循环找到时间复杂度，但我不确定while循环。 如果有人能帮助我找到每个代码的总运行时间，将不胜感激。
第一个代码示例几乎是循环的classis。 其复杂度为O（n ^ 2）。 这是因为内环具有复杂度O（n）并且它运行n次。
第二个有点困难，直到你看到它等同于非嵌套循环（忽略检查的复杂性）
int result = 0; int i = 0; while (i < n){ result += arr[i]; i += 1; } printf("%d\n", result);
意味着它的复杂性是O（n）
计算时间复杂度的最佳方法是尝试真正理解算法的工作原理并计算操作。 在第二个例子中，内部循环永远不会运行，直到外部循环处于最后一次迭代。 而且由于它们甚至执行相同的代码，整个过程可以简化为一个循环。
另一个很好的例子是：
for(i=0;i
让我们计算一下操作：1 + 2 + 3 + 4 + ... + n。 这归结为n * n / 2导致O（n ^ 2）
for循环，在一天结束时，是一个while循环。 forms的东西：
for(int i=0; i
相当于：
int i=0; while(i
事实上，在算法的纯数学分析中，您应该在算法中将任何for循环转换为while循环（有几个原因）。
回到你的代码。 分析很简单：
- 在while循环的第一次迭代之前，i的值为0. - 存在一个更新变量i（i ++）的唯一语句。 - 在外循环的每次迭代中，i增加1. - 外循环最多运行n次。
- 在任何循环的迭代之前，j的值为0. - 有2个语句更新j（j = 0和j ++） - 非正式：我们可以在内循环的任何迭代之前判断j的值是0 - 在内部循环中，更新j的唯一语句是j ++。 -on内循环j的每次迭代增加1.内循环最多n次由循环保护运行。
- 外循环最多运行n次，内循环最多运行n次，用于外循环的每次迭代。 所有其他陈述都是不变的。 算法在O（n * n）= O（n ^ 2）
第二个稍微复杂但是：
- 在外循环的第一次迭代之前，i的值为0. -Informally：外部循环将运行，直到i的值为（n / 2 - 1） - 更新语句（i + = 1）将i更新为（n / 2） - 非正式：内部循环运行（nn / 2 = n / 2）次，它只运行一次。 - 外环运行n / 2次，内环运行n / 2次恰好一次。
因此算法运行O（n / 2 + n / 2）= O（n）次