算法分析问题

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

---

它是否正确？可能不是这样我会改写:我哪里错了？

Answer 1

你是对的.O符号让您了解算法如何缩放,而不是绝对速度.如果您添加更多可能性,两种解决方案都将以相同的方式扩展,但其中一种解决方案的速度始终是另一种.

对于足够小的"n",O(n)运算也可能比O(n ^ 2)运算慢.想象一下,你的O(n)计算涉及5个平方根,而你的O(n ^ 2)解是一个单一的比较.对于小型数据集,O(n ^ 2)操作将更快.但是当n = 1000时,你正在进行5000平方根但1000000比较,那么O(n)可能会开始看起来更好.