2

我试图在我的算法中正确计算数学，但我很难理解计算 ie 等的“算法分析f(n) = 1” f(n) = n-1。

我创建了一个方法，它循环遍历一个排序的整数数组，并计算有多少不同的整数（即{1,3,3,3,5,6,8} = 5）。我如何计算最坏的情况？

基本上，代码是这样的：

int length = a.length;
int diffCount = 1; //The number of different integers

for(int i = 1; i < length; i++)
{
    int b = a[i];
    int c = a[i-1];

    if(c>b)
         throw new IllegalStateException("unsorted array");

    if(c!=b)
         diffCount++;
}
return diffCount;

那里还有一些其他的东西，但这只是为了防止像空数组之类的错误，所以我没有包括它。

这里最坏的情况是什么..？如果条件c!=b每次都为真？

4

3 回答 3

4

就运行时分析而言，如果数组已排序，则此算法始终为O(n) 。如果不是，它将在此之前抛出异常（但最坏的情况仍然是O(n)）。

根据值的不同，结果会略有不同。有关分支预测的解释，请参见彼得的答案。但我认为这不会显着影响运行时间。

于 2012-09-13T14:30:38.163 回答
1

从理论上讲，对于给定长度的数组，执行此循环所花费的时间将始终相同。

我查看了分支预测是否可能会受到影响，在这种情况下它似乎不太可能，因为 JIT 足够聪明，可以消除第二个分支。

在 C 中，可以删除分支

diffCount += c != b;

并且可能 JIT 会做类似的事情。

于 2012-09-13T14:21:59.823 回答
1

通常，在分析复杂性时，您会关注您认为算法中最慢的操作是什么。对于排序算法，我相信你会选择比较。在您的代码中，我会选择两个数组访问：

int b = a[i];
int c = a[i-1];

甚至两者的比较：

if (c != b) …

而不是diffCount++. 这意味着比较的结果并不重要，因为它总是会发生。

当然，您可以选择根据多个操作来分析复杂性。例如，对于排序，您可以查看元素交换以及元素比较。或者在您的情况下，您可能需要关注，diffCount++因为您希望内存写入比比较慢得多。

我选择的操作会得到命中a.length时间，所以这就是你的算法的复杂性。

If this chosen operation is under a condition, you have to pick (when looking for Big-O complexity) a reasonable upper bound on how often the condition can get hit. So, in your case, if it's possible for any input array that c != b is true for all pairs of elements checked, you can assume it's always true in your analysis.

于 2012-09-13T14:35:49.713 回答