为新的初学者
可能重复：
Big O的纯英文解释
最近我被问到关于如何使用Big O符号的知识，而且我之前因为从未遇到过Big O而感到难过。 我已经阅读了关于Big O的维基百科页面，并看了一些在Stackoverflow上发布的问题，但我只是不明白。
我的问题：有人能以最简单的形式提供Big O的解释，并提供如何在以下Java方法中使用它的示例：
public int getScore(int[] dice)
{
int[][] dups;
dups = possibleDups(dice);
// Set catScore
for (int[] i : dups)
{
for (int k = 0; k < i.length; k++)
{
if (i[k] > 0)
{
switch (i[k]) {
case 1:
catScore = Category.ONES;
break;
case 2:
catScore = Category.TWOS;
break;
case 3:
catScore = Category.THREES;
break;
case 4:
catScore = Category.FOURS;
break;
case 5:
catScore = Category.FIVES;
break;
case 6:
catScore = Category.SIXES;
break;
case 7:
catScore = Category.SEVENS;
break;
case 8:
catScore = Category.EIGHTS;
break;
default:
catScore = Category.NONE;
break;
}
}
}
}
return sumAll(dice);
}
大O是执行算法的最坏情况。 你应该看看你如何循环取决于内部循环。 样品：
public void doSomething(int n){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
}
最糟糕的情况是迭代100次。 将n更改为20，然后最差的情况是400次迭代。
这是O（n ^ 2）。
大O符号详细说明解决方案时间与集合中项目数量的比例差异。 它实际上没有提及解决方案需要多长时间才能解决问题，但它详细说明了解决解决方案的时间在知道固定点的时间以及您可能添加的其他项目的时间增长的速度。
因此，如果制作咖啡需要5分钟时间，那么计算Big O解决方案的信息还不够，但如果需要5分钟时间制作咖啡，5分钟时间制作10杯咖啡，5分钟时间制作100万杯咖啡那么它就是O（1），其中1表示一个单位的时间。
现在，如果你有一个单杯咖啡机，制作一杯咖啡需要大约两分钟的时间，制作两杯咖啡需要四分钟，制作十杯咖啡需要二十分钟，然后再花几分钟时间制作一些咖啡咖啡与杯子的数量成比例，使得大O符号O（x），意味着你需要X（每个咖啡一个）时间单位。
其他大O符号很常见，O（x ^ 2）O（xlog（x））等。它们都根据考虑的元素数量描述时间增长的比例。
请注意，对于一些小的项目集合，O（1）可能比O（x）解决方案慢，因为我们谈论的是时间单位，而不是实际时间。 因此，特定O（1）中的时间单位可能是一个小时，而O（x）解决方案中的特定时间单位可能是十分钟。 在这种情况下，O（x）解决方案可能会更快，直到您需要处理六个或更多项目。 从长远来看，较低权力的大O项（如O（1））总是会优于具有较高权力O（x）的项，无论实际时间单位有多大或多少。
在计算机科学中，大部分兴趣是“运行需要多长时间？”。 很多时候的答案是“它取决于输入的大小（但它可能不是）”。 Big-Oh特别是一个函数，它描述了一个算法运行多长时间的上限。 有一些数学细节（限制，渐近线等），但这是一个非常基本的观点。
在你的例子中，你遍历一个列表，然后遍历该列表中的所有内容，循环遍历另一个列表。 因此，算法运行的时间与列表的大小成正比。 如果你认为列表中有'n'个东西，而你的第二个列表中有m个东西，那么你的算法运行时间是O（m * n）。 如果m〜n，那么说O（n ^ 2）也是准确的。
对于地图，查找是恒定的时间（假设他们是）。 在这种情况下，Map查找的运行时间是O（c），它与O（1）相同。
链接地址: http://www.djcxy.com/p/39685.html上一篇: for anew beginner