logo标签列表

算法分析问题

algorithmbig-o
4

注意：我在算法分析方面是一个超级新手，所以不要将我的任何断言视为绝对真理，我陈述的任何事情（或一切）都可能是错误的。

嗨，我正在阅读有关算法分析和“大O符号”的内容，但有些事情让我感到困惑。

假设您被要求打印字符数组的所有排列，例如[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(n2)。

我认为还有其他的做法：

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(2)

这正确吗？可能不是，所以我会重新表述：我错在哪里？

4
对于字符数组 [a,b,c] 的所有排列为 abc、acb、bac、bca、cab 和 cba。 - quant_dev
你有测量第二个实现的速度吗？虽然迭代次数减少了一半，但 System.out.println 和字符串连接很可能是最慢的部分 - 你没有减少这些函数被调用的次数。 - Tom Leys
同意Tom Leys的观点。这正是大O符号省略常数的原因。否则，您将永远不知道应该包括哪些常数。 - Alex Gartrell
11个回答
13

你是正确的。O-符号告诉你算法的增长速度，而不是绝对速度。如果你增加更多可能性，两种解决方案的增长方式将相同，但其中一种方案始终会比另一种快两倍。

O(n) 操作在 'n' 很小的情况下可能比 O(n^2) 操作还慢。想象一下，你的 O(n) 计算需要进行 5 次平方根运算，而你的 O(n^2) 解决方案只是一个简单的比较操作。针对小型数据集，O(n^2) 操作将更快。但当 n=1000 且你正在执行 5000 次平方根运算和 1000000 次比较时，O(n) 可能会更好。

3

我认为大多数人都同意第一个是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)。

2

大O符号表示的是算法在输入大小变化时相对于自身的速度，而不是它本身的速度。

一个算法可能是O(1)，但需要一百万年才能完成。另一个算法可能是O(n^2)，但对于小的n值来说比O(n)算法更快。

此问题的一些答案可能有助于解决大O符号方面的疑问。此问题的答案也可能有所帮助。

1

你说得对。如果两个算法在大O符号表示法中等价，那么其中一个算法需要比另一个算法多花费一个恒定的时间量（“A比B多花费5分钟”），或者是一个倍数（“A比B慢5倍”），或者两者都有（“A比B慢2倍加上额外的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开始的快捷方式）。现在提供一种不同的方法：

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对象及其所有内部数据结构，并且因为它必须为每个整数计算哈希码。但是，如果您使用长度为1000万的数组进行尝试，您将发现完全不同的情况。第一个版本必须检查大约5000亿对数字（约为（N * N）/ 2）；第二个版本必须对大约2000万个数字执行哈希函数计算（约为2 * N）。在这种情况下，您肯定需要第二个版本！！
大O计算背后的基本思想是(1) 它相当容易计算（您不必担心CPU速度有多快或L2缓存是什么类型），以及(2) 谁会关心小问题...他们已经足够快了：真正困扰你的是大问题！这并不总是正确的（有时候缓存类型很重要，有时候在小数据集上表现如何也很重要），但它们足够接近真实情况，以便大O非常有用。
1

忽略将程序输出称为“排列”的问题：

大O符号省略常数系数。而2是一个常数系数。

因此，比原始程序快两倍的程序具有相同的O()是没有问题的。

0

理解大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符号。

0
一种思考大O的方法是考虑不同算法在非常不公平的情况下的表现。例如，如果一个算法在超级计算机上运行，而另一个算法在手表上运行，如果可以选择一个N值，使得即使较差的算法在超级计算机上运行，手表仍然能够先完成，则它们具有不同的大O复杂度。另一方面，如果你可以看到无论选择哪个算法或者N有多大，超级计算机总是会赢，那么两个算法必须按照定义具有相同的复杂度。
在你的算法中，更快的算法只比第一个算法快了两倍。即使N非常高，比如100万、1万亿甚至是格雷厄姆数，这也不足以让手表击败超级计算机，因此两个算法按照大O的定义具有相同的复杂度。
0

你说得对，它们都是大O n平方级别的算法。实际上，在你的问题中，当你说“现在这个算法比原来的算法快两倍”时，你已经证明了它们属于同一个大O级别。两倍的速度意味着乘以1/2，这是一个常数，因此根据定义它们属于相同的大O级别。

不一定是真的。例如，当n==2时，1/2 n^2 == n不成立。你需要展示这个1/2常数在很多N上都成立，以证明你的断言。 - Tom Leys
仍然在技术上是正确的。O(g(n)) 意味着松散地上界为 c*g(n)。O(n) 的每个元素也都属于 O(n^2)、O(n^3) 等等。 - Nick Lewis
1
@Tom Leys，根据定义，如果您有两个函数，并且可以将其中一个乘以常数以获得另一个，则它们属于相同的大O集合。不需要证明，这是符号的定义。 - Graphics Noob
0

假设我有一个算法可以在O（n）时间内完成相同的事情。现在假设我给你一个包含10000个字符的数组。你的算法需要n^2和（1/2）n^2的时间，即100,000,000和50,000,000。我的算法只需要10,000。显然，那个1/2的因素并没有起到作用，因为我的算法要快得多。 n^2项被认为支配像n和1/2这样的较小项，从本质上将它们变得可以忽略不计。

0

大O符号表示一组函数，因此说“这个东西是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了吗？）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接