我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?

比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?


当前回答

你可能会发现把它形象化很有用:

同样,在LogY/LogX尺度上,函数n1/2, n, n2都看起来像直线,而在LogY/X尺度上,2n, en, 10n是直线和n!是线性的(看起来像n log n)

其他回答

我是这样想的,你有一个任务,要清理一个由坏人V引起的问题,他选择了N,你必须估计出当他增加N时,你需要多长时间来完成你的问题。

O(1) ->增加N并没有什么不同

O(log(N)) ->每次V翻倍N,你必须花费额外的时间T来完成任务。V又翻倍了N,你花了同样多的钱。

O(N) -> V N每翻一倍,花费的时间就翻一倍。

O(N²)- V N每翻一倍,花费的时间就增加4倍。(这不公平!!)

O(nlog (N)) -, V每翻一倍N,你就花两倍的时间,再多一点。

这些是算法的边界;计算机科学家想要描述大n值需要多长时间(当你分解密码学中使用的数字时,这很重要——如果计算机速度提高了10倍,你需要多使用多少位才能确保它们仍然需要100年而不是1年才能破解你的加密?)

有些界限可能有奇怪的表达式,如果它对涉及的人有影响的话。我在Knuth的《计算机编程艺术》中见过类似于O(nlog (N) log(log(N))的算法。(我一时想不起是哪一个了)

你可能会发现把它形象化很有用:

同样,在LogY/LogX尺度上,函数n1/2, n, n2都看起来像直线,而在LogY/X尺度上,2n, en, 10n是直线和n!是线性的(看起来像n log n)

有人必须吸可卡因才能写出O(x!)吗?

不用,用Prolog就行。如果您在Prolog中编写排序算法,只需描述每个元素都应该比前一个元素大,并让回溯为您进行排序,那么它将是O(x!)也称为“排列排序”。

一种思考的方式是:

O(N²)意味着对于每个元素,你都要对其他元素做一些事情,比如比较它们。冒泡排序就是一个例子。

O(N log N)意味着对于每个元素,你只需要看log N个元素。这通常是因为你知道一些元素,可以让你做出有效的选择。最有效的排序就是一个例子,比如归并排序。

O(N!)表示对N个元素的所有可能排列进行处理。旅行推销员就是一个例子,那里有N!访问节点的方法,暴力解决方案是查看每一种可能的排列的总代价,以找到最优的一个。

我试图用c#和JavaScript给出简单的代码示例来解释。

C#

For List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};

O(1)看起来像

return numbers.First();

O(n)看起来像

int result = 0;
foreach (int num in numbers)
{
  result += num;
}
return result;

O(nlog (n))是这样的

int result = 0;
foreach (int num in numbers)
{
    int index = numbers.Count - 1;
    while (index > 1)
    {
        // yeah, stupid, but couldn't come up with something more useful :-(
        result += numbers[index];
        index /= 2;
    }
}
return result;

O(n2)是这样的

int result = 0;
foreach (int outerNum in numbers)
{
    foreach (int innerNum in numbers)
    {
        result += outerNum * innerNum;
    }
}
return result;

O(n!)看起来,嗯,太累了,想不出任何简单的东西。 但我希望你能明白大意?


JavaScript

对于const数= [1,2,3,4,5,6,7,12,543,7];

O(1)看起来像

numbers[0];

O(n)看起来像

let result = 0;
for (num of numbers){
    result += num;
}

O(nlog (n))是这样的

let result = 0;
for (num of numbers){

    let index = numbers.length - 1;
    while (index > 1){
        // yeah, stupid, but couldn't come up with something more useful :-(
        result += numbers[index];
        index = Math.floor(index/2)
    }
}

O(n2)是这样的

let result = 0;
for (outerNum of numbers){
    for (innerNum of numbers){
        result += outerNum * innerNum;
    }
}