1

我正在准备考试，在运行时分析方面遇到了一些麻烦。我有以下两种方法，我对运行时分析感到困惑：

 public boolean findDuplicates(String [] arr) {
    Hashtable<String,String> h = new Hashtable<String,String>();
    for (int i = 0; i < arr.length; i++) {
         if (h.get(arr[i]) == null)
              h.put(arr[i], arr[i]);
         else
              return true;
         }
    return false;
    }

假设散列函数只在任何键上采用 O(1)，运行时间是否会简单地为 O(n)，因为在最坏的情况下，运行整个数组？如果每个散列函数需要恒定的时间来评估，我是否会沿着正确的思路考虑这一点？

我遇到的另一个问题似乎要复杂得多，我不知道如何解决这个问题。假设这些是arrarlists。

public boolean makeTranslation(List<Integer> lst1, List<Integer> lst2) {
//both lst1 and lst2 are same size and size is positive
     int shift = lst1.get(0) - lst2.get(0);
     for (int i = 1; i < lst1.size(); i++)
          if ( (lst1.get(i) - lst2.get(i)) != shift)
               return false;
     return true;
}

在这种情况下，get 操作应该是恒定的，因为我们只是检索特定的索引值。但是在 for 循环中，我们既将其与 shift 进行比较，也对所有元素进行迭代。这将如何准确地转换为运行时间？

一个有用的解释将不胜感激，因为我比本课程中的任何内容都最难理解运行时分析，而我的期末考试是下周。

4

4 回答 4

1

简短的回答：这两种方法的时间复杂度都是O(n).

对于散列，很明显get和put操作都需要恒定的时间。

对于列表，如果您使用ArrayList实现（并且很可能），该get方法也需要恒定的时间。这是因为ArrayListJava 中的 aList是由数组支持的 a。

ArrayList.get(index)标准 Java 库中的代码：

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

RangeCheck大概做了两次比较，都是常数时间。从 an 返回一个值array显然是常数时间。因此，该get方法ArrayList需要恒定的时间。

至于您在 OP 中提到的具体问题：

但是在 for 循环中，我们既将其与 shift 进行比较，也对所有元素进行迭代。这将如何准确地转换为运行时间？

lst1.get(i)需要恒定的时间。lst2.get(i)需要恒定的时间。因此，lst1.get(i) - lst2.get(i)需要恒定的时间。对于(lst1.get(i) - lst2.get(i)) != shift. 这个想法是恒定数量的恒定时间操作的总和仍然是恒定时间。由于循环最多迭代n次数，因此总时间为O(Cn)，即 O(n)，其中 C 是常数。

而且......在final之前简要回顾一下大O符号永远不会有什么坏处:)

于 2012-12-05T02:52:24.367 回答
0

Big-O 表示法不是很准确，因为您忽略了常数因子和低阶项。因此，即使您有 2 个恒定操作 n 次，它仍然是 O(n)。实际上，它将是 (1+1)n=2n，但在 ordo 表示法中，我们将其四舍五入（即使它是 10000n）。因此，对于这两种情况，运行时间都是 O(n)。

在实践中，我建议在最坏的情况下输入每个循环和每个操作的成本。从最里面的嵌套级别开始并向外相乘（只有每个级别的最高成本）。

例如：

for (int i = 0; i<n; i++) { //n times
    //log n operation
    for (int i = 0; i<n; i++) { //n times
        //constant operation
    }
}

在这里，我们有 n*(log(n)+n*1)=O(n*n) 因为 n>log(n)

于 2012-12-05T01:23:02.227 回答
0

通常， O() 表示算法的复杂性，通常是操作的数量，假设每个操作的成本是恒定的。例如O(1000n)类似于编写O(n)，因为每个操作成本1000，并且有n次操作。

因此，假设get和put对于每个值都是恒定的（取决于库实现），那么两者的时间都是O(n)。欲了解更多信息，请参阅： http ://en.wikipedia.org/wiki/Big_O_notation

于 2012-12-05T01:29:18.810 回答
0

值得一提的是，但这两个操作都是O(n)（对于#2，这是最坏的情况）。需要注意的关键是每次迭代完成的关键操作的数量。

对于您的第一个片段，这Hashtable有点牵强，因为访问时间不会是您在循环中最大的操作。情况也是如此，因为那Hashtable只是new'd，你总是会在其中插入n 个元素。

对于您的第二个片段，您有机会提前结束。如果下一个元素的差异不是shift，那么您false就在那儿返回，然后，这只是一个操作。在最坏的情况下，您将经历所有n并返回。

于 2012-12-05T03:23:28.530 回答