大O - 总是输入的大小？

Question

我编写了自己的面试风格问题,并对我解决方案的大问题提出了疑问.我将在下面说明问题和我的解决方案,但首先让我说明显的解决方案涉及嵌套循环并且是O(n ²).我相信我找到了一个O(n)解决方案,但后来我意识到它不仅取决于输入的大小,还取决于输入的最大值.看起来我的O(n)的运行时间只是技术性的,它可以很容易地在O(n ²)时间运行或在现实生活中更糟.

问题是:对于给定正整数数组中的每个项目,打印数组中所有其他项目,这些项目是当前项目的倍数.

示例输入:

[2 9 6 8 3]

示例输出:

2: 6 8
9:
6:
8:
3: 9 6

我的解决方案(在C#中):

private static void PrintAllDivisibleBy(int[] arr)
{
    Dictionary<int, bool> dic = new Dictionary<int, bool>();
    if (arr == null || arr.Length < 2)
        return;

    int max = arr[0];
    for(int i=0; i<arr.Length; i++)
    {
        if (arr[i] > max)
            max = arr[i];
        dic[arr[i]] = true;
    }

    for(int i=0; i<arr.Length; i++)
    {
        Console.Write("{0}: ", arr[i]);
        int multiplier = 2;
        while(true)
        {
            int product = multiplier * arr[i];
            if (dic.ContainsKey(product))
                Console.Write("{0} ", product);

            if (product >= max)
                break;
            multiplier++;
        }
        Console.WriteLine();
    }
}

因此,如果2个数组项为1和n,其中n是数组长度,则内部while循环将运行n次,使其等效于O(n ²).但是,由于性能取决于输入值的大小,而不是列表的长度,这使得它成为O(n),对吗？

你会认为这是一个真正的O(n)解决方案吗？是否只有O(n)由于技术性,但在现实生活中更慢？

Answer 1

好问题！答案是，不，n并不总是输入的大小：如果不定义其含义，你就无法真正谈论它，但人们经常使用不精确的语言并暗示这是“这里缩放的最明显的东西”。从技术上讲，我们通常应该说“这种排序算法执行列表中元素数量的多次比较”：具体说明我们正在测量的是什么以及数量（比较）。O(n)nnO(n)n

如果您有一个算法取决于两个不同事物的乘积（这里是列表的长度和其中最大的元素），则表达它的正确方法是形式O(m*n)，然后为您的上下文定义什么m和是n。因此，我们可以说您的算法执行O(m*n)乘法，其中m是列表的长度，n是列表中最大的项目。