我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
一种思考的方式是:
O(N²)意味着对于每个元素,你都要对其他元素做一些事情,比如比较它们。冒泡排序就是一个例子。
O(N log N)意味着对于每个元素,你只需要看log N个元素。这通常是因为你知道一些元素,可以让你做出有效的选择。最有效的排序就是一个例子,比如归并排序。
O(N!)表示对N个元素的所有可能排列进行处理。旅行推销员就是一个例子,那里有N!访问节点的方法,暴力解决方案是查看每一种可能的排列的总代价,以找到最优的一个。
其他回答
把它想象成垂直堆叠乐高积木(n),然后跳过它们。
O(1)表示在每一步,你什么都不做。高度保持不变。
O(n)表示在每一步,你堆叠c块,其中c1是常数。
O(n²)表示在每一步,你堆叠c2 x n个块,其中c2是一个常数,n是堆叠块的数量。
O(nlogn)表示在每一步,你堆叠c3 x n x logn个块,其中c3是一个常数,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;
}
}
不,O(n)算法并不意味着它将对每个元素执行操作。大o符号给了你一种方法来谈论你的算法的“速度”独立于你的实际机器。
O(n)表示算法花费的时间随着输入的增加而线性增长。O(n²)意味着你的算法花费的时间是你输入的平方。等等。
为了对被问到的问题保持真诚,我会用回答8岁孩子的方式来回答这个问题
假设一个冰淇淋小贩准备了许多不同形状的冰淇淋(比如N个),按顺序排列。 你想吃中间的冰淇淋
情况1:只有吃完所有比它小的冰淇淋,你才能吃冰淇淋 你将不得不吃掉一半准备好的冰淇淋(输入)。答案直接取决于输入的大小 解是o(N)阶的
情况2:—你可以直接吃中间的冰淇淋
解是O(1)
情况3:只有当你吃完所有比它小的冰淇淋时,你才能吃冰淇淋,每次你吃冰淇淋时,你都允许另一个孩子(每次都是新孩子)吃掉他所有的冰淇淋 总时间为N + N + N.......(N/2)次 溶液是O(N2)
我会试着为一个真正的八岁男孩写一个解释,除了专业术语和数学概念。
比如O(n²)的运算会怎样?
如果你在一个聚会上,包括你在内有n个人。需要多少次握手才能让每个人都和其他人握手,因为人们可能会在某个时候忘记他们握手的人是谁。
注意:这近似于产生n(n-1)的单形,这足够接近于n²。
如果一个操作是O(nlog (n))这是什么意思?
你最喜欢的球队赢了,他们站在队伍里,队伍里有n名球员。你需要和每个玩家握手多少次,假设你要和每个玩家握手多次,多少次,玩家的号码n中有多少位数字。
注意:这将产生n * log n的10次方。
有人必须吸可卡因才能写出O(x!)吗?
你是一个富二代,你的衣柜里有很多衣服,每种衣服有x个抽屉,抽屉一个挨着一个,第一个抽屉里有一件衣服,每个抽屉里有和左边抽屉一样多的衣服,所以你有一顶帽子,两顶假发,…(x-1)条裤子,然后是x件衬衫。现在,用每个抽屉里的一件物品,你能装扮出多少种风格呢?
注意:这个例子表示一个决策树中有多少个叶结点,其中子结点数=深度,通过1 * 2 * 3 *完成。* x