查找给定代码的复杂性

Question

我正在努力寻找给定代码的复杂性。我想我正在努力确定正确的复杂性以及如何实际分析复杂性。待分析代码如下：

    public void doThings(int[] arr, int start){
    boolean found = false;
    int i = start;
    while ((found != true) && (i<arr.length)){
        i++;
        if (arr[i]==17){
            found=true;
        }
    }
}
public void reorganize(int[] arr){
    for (int i=0; i<arr.length; i++){
        doThings(arr, i);
    }
}

The questions are:

1) reorganize 方法的最佳情况复杂度是多少？它针对哪些输入发生？
2) 重组方法的最坏情况复杂度是多少？它发生在什么输入下？

My answers are:

1) 对于重组方法，可能会出现两种最佳情况。第一个是当数组长度为 1 时，这意味着 reorganize 和 doThings 方法中的循环将运行恰好一次。另一种可能性是当数组的第 i 个项目是 17 时，这意味着 doThings 循环不会在第 i 个迭代中完全运行。因此，在这两种情况下，最好的情况=O(n).

2) 最坏的情况是数字 17 在数组的末尾，而数字 17 不在数组中。这将意味着数组将被遍历 n×n 次，这意味着最坏的情况将是 Ο(n^2)。

Could anyone please help me answer the questions correctly, if mine is incorrect and if possible explain the problem?

Answer 1

"best case" 数组是空的，你什么都不搜索。

最坏的情况是你查看每一个元素，因为你永远看不到 17。所有其他情况都介于两者之间。

if (arr[i]==17){ 是代码的 "hottest path"，意思是运行最常见。

在最坏的情况下，它总是会执行总共 n*(n-1)/2 次（我想我做的数学是正确的），因为即使你设置了 found = true，reorganize 方法也不会知道了这一点，并没有结束，继续搜索，即使你已经扫描了整个阵列。

基本上，没有方法的扁平化代码。你有这个问题。

What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?

查找给定代码的复杂性

Finding the complexity of given code

algorithm

complexity-theory

time-complexity