algorithm - 算法分析题

Question

注意：我是算法分析的超级新手，所以不要将我的任何肯定作为绝对真理，我所说的任何（或一切）都可能是错误的。

嗨，我正在阅读有关算法分析和“Big-O-Notation”的内容，我对某些事情感到困惑。

假设要求您打印 char 数组的所有排列，对于 [a,b,c]，它们将是 ab、ac、ba、bc、ca 和 cb。

一种方法是（在Java中）：

for(int i = 0; i < arr.length; i++)
    for(int q = 0; q < arr.length; q++)
        if(i != q)
            System.out.println(arr[i] + " " + arr[q]);

如果我是正确的，这个算法有一个O(n ² )的符号。

我想到了其他方法：

for(int i = 0; i < arr.length; i++)
    for(int q = i+1; q < arr.length; q++)
    {
        System.out.println(arr[i] + " " + arr[q]);
        System.out.println(arr[q] + " " + arr[i]);
    }

现在这个算法的速度是原来的两倍，但除非我错了，否则对于大 O 表示法它也是O( ² )

它是否正确？可能不是，所以我会改写：我哪里错了？

score 13 · Accepted Answer

你是对的。O-notation 让您了解算法的扩展方式，而不是绝对速度。如果您添加更多可能性，这两种解决方案将以相同的方式扩展，但一种总是比另一种快两倍。

对于足够小的“n”，O(n) 操作也可能比 O(n^2) 操作慢。想象一下，您的 O(n) 计算涉及取 5 个平方根，而您的 O(n^2) 解决方案是一次比较。对于小数据集，O(n^2) 操作会更快。但是当 n=1000 并且您进行 5000 平方根但进行 1000000 次比较时，O(n) 可能会开始看起来更好。

score 3 · Accepted Answer

我认为大多数人都同意第一个是 O(n^2)。每次外循环运行时，外循环运行 n 次，内循环运行 n 次。所以运行时间是O(n * n), O(n^2)。

第二个是 O(n^2) 因为外部循环运行 n 次。内部循环运行 n-1 次。平均而言，对于这个算法，内循环对每个外循环运行 n/2 次。所以这个算法的运行时间是 O(n * n/2) => O ( 1/2 * n^2) => O(n^2)。

score 2 · Accepted Answer

Big-O 表示法没有说明算法的速度，只是当输入的大小发生变化时它相对于自身的速度有多快。

一个算法可能是 O(1) 却需要一百万年。另一种算法可能是 O(n^2)，但比小 n 的 O(n) 算法更快。

这个问题的一些答案可能有助于大 O 表示法的这一方面。这个问题的答案也可能会有所帮助。

score 1 · Accepted Answer

忽略调用程序输出“排列”的问题：

Big-O-Notation 省略了常数系数。2 为常数系数。

因此，对于比原来快两倍的程序具有相同的 O() 并没有错

score 1 · Accepted Answer

你是对的。两种算法在 Big O 表示法中是等价的，如果其中一个算法花费的时间固定不变（“A 比 B 多花 5 分钟”），或者是倍数（“A 比 B 长 5 倍”），或者两者兼而有之（“A对于所有大小的输入，需要 2 倍 B 加上额外的 30 毫秒")。

这是一个使用根本不同的算法来解决类似问题的示例。首先，较慢的版本，它看起来很像你原来的例子：

boolean arraysHaveAMatch = false;
for (int i = 0; i < arr1.length(); i++) {
    for (int j = i; j < arr2.length(); j++) {
        if (arr1[i] == arr2[j]) {
            arraysHaveAMatch = true;
        }
    }
}

这具有 O(n^2) 行为，就像您的原始行为一样（它甚至使用您发现的从 i 索引而不是从 0 开始 j 索引的相同快捷方式）。现在这是一种不同的方法：

boolean arraysHaveAMatch = false;
Set set = new HashSet<Integer>();
for (int i = 0; i < arr1.length(); i++) {
    set.add(arr1[i]);
}
for (int j = 0; j < arr2.length(); j++) {
    if (set.contains(arr2[j])) {
        arraysHaveAMatch = true;
    }
}

现在，如果您尝试运行这些，您可能会发现第一个版本运行得更快。至少如果您尝试使用长度为 10 的数组。因为第二个版本必须处理创建 HashSet 对象及其所有内部数据结构，并且因为它必须为每个整数计算哈希码。但是，如果您尝试使用长度为 10,000,000 的数组，您会发现一个完全不同的故事。第一个版本必须检查大约 50,000,000,000,000 对数字（大约 (N*N)/2）；第二个版本必须对大约 20,000,000 个数字（大约 2*N）执行散列函数计算。在这种情况下，你当然想要第二个版本！！

Big O 计算背后的基本思想是（1）它相当容易计算（您不必担心 CPU 的速度或它具有哪种 L2 缓存等细节），以及（2）谁在乎小问题......无论如何它们都足够快：这是会杀死你的大问题！情况并非总是如此（有时它对你拥有什么样的缓存很重要，有时它对小数据集的性能有多好很重要），但它们通常足够接近真实，足以让 Big O 有用。

score 0 · Accepted Answer

思考大 O 的一种方法是考虑即使在非常不公平的情况下，不同算法的表现如何。例如，如果一个运行在非常强大的超级计算机上，而另一个运行在手表上。如果可以选择一个很大的 N，即使在超级计算机上运行更糟糕的算法，手表仍然可以先完成，那么它们就有不同的大 O 复杂度。另一方面，如果您可以看到超级计算机将永远获胜，无论您选择哪种算法或您的 N 有多大，那么根据定义，两种算法必须具有相同的复杂性。

在您的算法中，较快的算法仅是第一个算法的两倍。这对于手表击败超级计算机的优势还不够，即使N非常高，100万，1万亿，甚至格雷厄姆的数字，怀表也永远无法以这种算法击败超级计算机。如果他们交换算法，情况也是如此。因此，根据 Big O 的定义，这两种算法具有相同的复杂性。

score 0 · Accepted Answer

你是对的，他们都是大 O n 平方，当你说“现在这个算法比原来的算法快两倍”时，你实际上证明了这一点在你的问题中是正确的。两倍快意味着乘以 1/2，这是一个常数，所以根据定义，它们在同一个大 O 集中。

score 0 · Accepted Answer

假设我有一个算法可以在 O( n ) 时间内做同样的事情。现在还假设我给了你一个 10000 个字符的数组。您的算法将花费n ^2 和 (1/2) n ^2 时间，即 100,000,000 和 50,000,000。我的算法需要 10,000。显然，1/2 的因素没有什么不同，因为我的速度要快得多。据说n ^2 项支配了较小的项，如n和 1/2，基本上使它们可以忽略不计。

score 0 · Accepted Answer

big-oh 符号表示一个函数族，所以说“这个东西是 O(n²)”意味着什么

这不是迂腐，这是理解这些事情的唯一正确方法。

O(f) = { g | 存在 x_0 和 c 使得对于所有 x > x_0，g(x) <= f(x) * c }

现在，假设您正在计算算法在最坏情况下根据输入大小执行的步骤：调用该函数 f。如果 f \in O(n²)，那么你可以说你的算法有 O(n²) 的最坏情况（但也有 O(n³) 或 O(2^n)）。常量的无意义源于定义（见 c？）。

score 0 · Accepted Answer

理解 Big-O 符号的最好方法是从数学上掌握符号背后的思想。查找单词“渐近线”的字典含义

A line which approaches nearer to some curve than assignable distance, but, though
infinitely extended, would never meet it.

这定义了最大执行时间（假想的，因为渐近线在无穷远处与曲线相交），所以你所做的一切都将在那个时间之内。
有了这个想法，您可能想知道 Big-O、Small-O 和 omega 表示法。

score -1 · Accepted Answer

永远记住，大 O 表示法代表“最坏情况”的情况。在您的示例中，第一个算法的平均情况是完整的外部循环 * 完整的内部循环，所以它当然是 n^2。因为第二种情况有一个实例，它几乎是完整的外部循环 * 完整的内部循环，它必须集中到同一堆 n^2 中，因为这是最坏的情况。从那里它只会变得更好，与第一个函数相比，你的平均值要低得多。无论如何，随着 n 的增长，您的函数时间会呈指数增长，这就是 Big O 真正告诉您的全部内容。指数曲线可以变化很大，但归根结底，它们都是同一类型。

algorithm - 算法分析题

11 回答 11

Related

Reference