如何计算这个简单算法的最坏情况 运行 时间复杂度
How to work out worst-case run time complexity of this simple algorithm
我正在尝试学习如何计算出最坏情况 运行 时间复杂度，我想知道是否有人可以通过突出显示所有操作等详细解释如何为下面的代码计算出它。 .. 对于糟糕的代码示例，我深表歉意，我很清楚这是有史以来最没有意义的方法！
public int two(int[] n){
int twosFound=0;
int other=0;
for (int i = 0; i < n.length; i++) {
if (n[i]==2) {
System.out.println("2 is found");
twosFound++;
}
else other++;
}
return twosFound;
}
如果O(n)的时间复杂度（实际上，exactly n）因为控制访问all n 数组的元素。 （加上没有额外的条件来终止循环）
从基本构建块开始，然后逐步向上：
- 初始化一个
int变量不依赖于数组长度，因此它是O(1)。
- （顺便说一句，当你想谈论 O(n) 时调用数组
n 是一个糟糕的主意。这很容易导致混淆。）
- 访问
n.length需要常数时间。另一方面，如果 n 是链表或其他数据结构，则需要进一步分析它。
- 访问
n[i] 需要常数时间。
System.out.println 需要常数时间，因为它既不依赖于数组长度也不依赖于数组内容。- 增加一个
int 变量需要常数时间。
if 语句采用了其组成部分所采用的最坏情况；在这种情况下，它是常数时间。for 循环在数组上线性迭代，因此它需要 O(n.length)，乘以 O(无论 [=18= 体内发生什么] 声明).- 在这种情况下，这是 O(n) * O(1) = O(n)。
您的最坏情况的复杂性与其他情况没有区别。这是因为你的算法。它的 运行ning 时间完全取决于数组中元素的数量。您测试每个元素以满足条件，您拥有的元素越多，算法达到 运行 所需的时间就越长。
其实很明显时间复杂度是O(number_of_elements)。这意味着时间与元素的数量成线性关系。如果你采用两倍大的数组，时间也会增加两倍。
我正在尝试学习如何计算出最坏情况 运行 时间复杂度，我想知道是否有人可以通过突出显示所有操作等详细解释如何为下面的代码计算出它。 .. 对于糟糕的代码示例，我深表歉意，我很清楚这是有史以来最没有意义的方法！
public int two(int[] n){
int twosFound=0;
int other=0;
for (int i = 0; i < n.length; i++) {
if (n[i]==2) {
System.out.println("2 is found");
twosFound++;
}
else other++;
}
return twosFound;
}
如果O(n)的时间复杂度（实际上，exactly n）因为控制访问all n 数组的元素。 （加上没有额外的条件来终止循环）
从基本构建块开始，然后逐步向上：
- 初始化一个
int变量不依赖于数组长度，因此它是O(1)。 - （顺便说一句，当你想谈论 O(n) 时调用数组
n是一个糟糕的主意。这很容易导致混淆。） - 访问
n.length需要常数时间。另一方面，如果n是链表或其他数据结构，则需要进一步分析它。 - 访问
n[i]需要常数时间。 System.out.println需要常数时间，因为它既不依赖于数组长度也不依赖于数组内容。- 增加一个
int变量需要常数时间。 if语句采用了其组成部分所采用的最坏情况；在这种情况下，它是常数时间。for循环在数组上线性迭代，因此它需要 O(n.length)，乘以 O(无论 [=18= 体内发生什么] 声明).- 在这种情况下，这是 O(n) * O(1) = O(n)。
您的最坏情况的复杂性与其他情况没有区别。这是因为你的算法。它的 运行ning 时间完全取决于数组中元素的数量。您测试每个元素以满足条件，您拥有的元素越多，算法达到 运行 所需的时间就越长。
其实很明显时间复杂度是O(number_of_elements)。这意味着时间与元素的数量成线性关系。如果你采用两倍大的数组，时间也会增加两倍。