查找给定代码的复杂性

我正在努力寻找给定代码的复杂性。我想我正在努力识别正确的复杂性，以及如何真正分析复杂性。要分析的代码如下：查找给定代码的复杂性

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); 
    } 
}

的问题是：

1）什么是整编方法和它发生什么样的输入最好的情况下的复杂性？
2）重组方法的最坏情况复杂度和它发生了什么输入？

我的答案是：

1）对于重新组织方法有可能出现的两种可能的最好的情况下。首先是数组长度为1时，这意味着reorganize和doThings方法中的循环只能运行一次。另一种可能性是，当数组的第i项是17时，意味着doThings循环不会在第i次迭代中完全运行。因此，在这两种情况下，最好的情况=Ο（n）。

2）最糟糕的情况是当数字17在数组的末尾，而数字17不在数组中时。这将意味着该阵列将被遍历n×n次，这意味着最坏的情况将是Ο（n^2）。

任何人都可以请帮助我正确回答问题，如果我的不正确，并且如果可能的话解释问题？

来源

2016-11-10 amine

重组是一个可怕的名字。它只是搜索 –

我没有看到'nxn' ...对我来说，只是'O（n）'在这两种情况下 – Hackerman

“最好的情况下”数组是空的，你什么也没有搜索。

最糟糕的情况是，你看每一个元素，因为你从来没有看到17.所有其他案件之间。

if (arr[i]==17){是代码的“最热门路径”，这意味着它最常运行。

它将始终执行共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?

来源

2016-11-10 15:17:17

查找给定代码的复杂性

回答

相关问题