如何在O（n）时间或O（nlogn）运行一个算法？
这个问题在这里已经有了答案：
那么我的第一个答案是...
算法的O（）表示法（虽然它可以应用于任何函数）有点像算法增长率的上限。 您可能担心的情况是与您的算法对给定输入大小执行的操作次数相关的函数。 你似乎要求一步一步的方法，所以我会尝试一个：
编写一个函数，用于描述算法针对n的输入大小（或n个元素的现有数据结构等）执行的最差操作次数。
使用Big-O符号的定义简化该函数。 大多数情况下，这非常简单; 然而，有些场合需要理解数学形式主义以及大O真正的含义。 在这里我不会介绍这些，因为对于教科书或CS教授来说这是一个更好的工作。 忽略细节，你可以在最大的函数中保留这个术语（如果它是一个术语的总和）并且摆脱所有其他的东西。 如果这个术语有任何常数系数，那就把它们除掉。 例如：f（n）= 4n ^ 2 + 10000n + 500将按前面描述的方式修改为n ^ 2，因为4n ^ 2项增长得快于另外两项并且系数4被丢弃; 留下n ^ 2。
下面是一个例子：可以说，List是一个数组数组，而lSize是数组中的项数。
for (int i=0; i < lSize; ++i){
for (int j = i+1; j<=lSize; ++j){
if (List[i] > List[j]){ //swap the elements
int temp = List[i];
List[i] = List[j];
List[j] = temp;
}
}
}
我们来计算使用上面显示的选择排序算法对n个项目列表进行排序所需的数字操作。
步骤1
对于列表大小n，该算法需要排序多少个操作（以n为单位）？ 这里lSize取值为n。 我们有两个for循环，一个嵌套在另一个内。 外部循环很简单，它为列表中的每个元素执行一次; 或n次。 在那个循环内部是另一个循环，其操作次数并不是很明显。 这个循环的迭代次数取决于外循环中的i的当前值。 如果你坐下来测试一些测试值并写出出现的系列，你会看到内部循环首先运行n次，然后（n-1）次然后是（n-2）次，依此类推，总计数描述如下： n +（n-1）+（n-2）... 2 + 1.你会注意到这是从1到n的所有数字的总和。 如果n = 100，那么内部循环的总迭代次数将为100 + 99 + 98 + 97 ... 2 + 1。这是一个算术级数，可以简化为n项：n *（n- 1）/ 2。 这是内循环内的操作得到评估的次数。 由于在内部循环内有3个操作，这意味着n个项目的操作总数是3 * n *（n-1）/ 2。 （3/2）n ^ 2-（3/2）n更容易在下一部分中重写。
第2步
我们现在有我们的功能。 其中f（）是我们的算法f（n）=（3/2）n ^ 2-（3/2）n所执行的操作次数。 显然，增长最快的词是（3/2）n ^ 2，所以我们放弃了（3/2）n。 这留下（3/2）n ^ 2我们摆脱（3/2）系数。 这留下n ^ 2。 因此，我们可以说f（n）是O（n ^ 2）。
这基本上是用O（）表示法描述算法的方法。 这忽略了重要的事情，并描述了一个用于产生答案的无脑秘诀。 为什么用这种方式总结算法？ 为什么可以忘记一个术语或系数？ 这些问题的答案可以在更严格的教科书描述中找到。
我希望我没有犯任何可怕的错误，这有点晚。
复杂性取决于您的输入是什么以及您的算法用于计算输出的变量。
一些简单的例子可以帮助您理解基本的算法复杂性：
以下是O（n）
// This is O(n)
for (int i = 0; i < array.length; i++) {
sum += array[i];
}
// This is O(n)
for (int i = 0; i < array.length / 2; i++) {
sum += array[i];
}
// This is O(n)
for (int i = 0; i < array.length / 200; i++) {
sum += array[i];
}
因为迭代次数总是取决于数组的大小（这里是N）。
但这是O（1）：
// This is O(1)
array[i]; // where i is an int
// This is O(1)
for (int i = 0; i < 10000; i++) {
sum += array[i % array.length];
}
无论阵列的大小如何：1或10,000或10 teras ...
这是O（n ^ 2）：
// O(n) that contain O(n) operation => O(n^2)
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) { // O(n)
sum += matrix[i][j];
}
}
假设这是一个方矩阵（否则内循环将在O（m）中运行）
有很多着名的算法需要研究，以便知道如何很好地计算算法的复杂性。 例如，对于O（log（n））复杂性，请查看：http://en.wikipedia.org/wiki/Binary_search_algorithm
在评估真实世界算法时，某些操作的复杂性可能隐藏在用于存储值的表示中。 例如，在Java中，您有ArrayList（a）和LinkedList（ll），它们可以与接口List（l）一起使用。 所以下面一行：
l.get（ⅰ）; //我是int并且l是List。
可能需要O（1）次或O（n）次，具体取决于列表的真实结构。
你可以阅读这些页面获取更多信息：http://en.wikipedia.org/wiki/Analysis_of_algorithms http://en.wikipedia.org/wiki/Computational_complexity_theory算法复杂度时间
首先，你可以通过以下方式学习这种类型的东西：
阅读描述算法并分析其复杂性的教科书（或研究论文，或其他资源），或者
自己分析算法; 即做数学。
当你有足够的经验时，你可以选择一些直观的捷径来估计算法的复杂性。
有人建议用一种技术来衡量问题大小变量（或变量）的一系列值的性能，绘制它们并尝试拟合曲线。 但是，这有一些问题：
总之，这种方法通常不能给出可靠的答案。
链接地址: http://www.djcxy.com/p/39355.html上一篇: How can I learn if an algorithm runs in O(n) time, or O(nlogn)?
下一篇: What is the time complexity of these dependent nested loops?