大O符号的复杂性排序是什么？
题
嗨，我试图了解大O符号的复杂程度是什么。 我已经阅读了很多文章，但还没有找到任何解释“复杂性的顺序”的东西，即使是在这里对大O的有用描述。
我已经了解了大O.
我已经理解的部分。 关于Big O表示法是，我们用输入大小n的增长来衡量算法的时间和空间复杂度。 我也明白，某些排序方法对于大O如O（n），O（n ^ 2）等具有最佳，最差和平均的场景，并且n是输入大小（要排序的元素的数量）。
任何简单的定义或例子将不胜感激谢谢。
大O是为某些功能的增长找到一个上限。 请参阅维基百科http://en.wikipedia.org/wiki/Big_O_notation上的正式定义
因此，如果你有一个算法对大小为n的数组进行排序，并且只需要一定数量的额外空间，并且需要（例如） 2 n² + n步骤来完成，那么你会说它的空间复杂度是O(n)或O(1) （取决于你是否计算输入数组的大小），它的时间复杂度是O(n²) 。
只知道那些O数字，你可以粗略地确定从n到n + 100或2 n或者你感兴趣的任何东西需要多少空间和时间。这就是算法“缩放”的程度。
更新
大O和复杂性对于同样的事情实际上只是两个术语。 你可以说“线性复杂性”而不是O(n) ，二次复杂性而不是O(n²)等等......
大O分析是运行时分析的一种形式，它根据输入大小的函数计算算法的运行时间来衡量算法的效率。 这不是一个正式的基准，只是在处理非常大的输入大小时通过相对效率对算法进行分类的一种简单方法。
更新：任何运行时分析的最快运行时间都是O（1），通常称为常量运行时间。具有恒定运行时间的算法总是需要相同的时间量来执行，而不管输入大小如何。这是算法的理想运行时间，但很难实现。 大多数算法的性能取决于n，输入的大小。算法可以按照最佳性能分类如下：
O（log n） - 如果算法的运行时间与输入大小成比例地递增，则算法被认为是对数的。
O（n） - 线性算法的运行时间与输入大小成正比增加。
O（n log n） - 超线性算法在线性算法和多项式算法之间。
O（n ^ c） - 多项式算法根据输入的大小快速增长。
O（c ^ n） - 指数算法比多项式算法增长得更快。
O（n！） - 一个因子算法增长最快，并且即使n的值很小也很快无法使用。
随着n变大，算法的不同顺序运行时间迅速分离。考虑每个算法类的运行时间
n = 10:
log 10 = 1
10 = 10
10 log 10 = 10
10^2 = 100
2^10= 1,024
10! = 3,628,800
Now double it to n = 20:
log 20 = 1.30
20 = 20
20 log 20= 26.02
20^2 = 400
2^20 = 1,048,576
20! = 2.43×1018
寻找一种在超线性时间或更好时间内工作的算法可以对应用程序的执行效果产生巨大影响。
说，当且仅当存在C和n0使得对于大于n0的所有n， f(n) < C*g(n) f(n) in O(g(n))中的f(n) < C*g(n)
现在这是一个相当数学的方法。 所以我会举一些例子。 最简单的情况是O（1）。 这意味着“不变”。 因此，无论程序的输入（n）有多大，都需要相同的时间才能完成。 常量程序的一个例子是采用整数列表并返回第一个整数的程序。 无论列表多长时间，您都可以先拿到第一张，然后立即退还。
下一个是线性的，O（n）。 这意味着如果程序的输入大小加倍，执行时间也会增加。 线性程序的一个例子是整数列表的总和。 你必须看看每个整数一次。 因此，如果输入是大小为n的列表，则必须查看n个整数。
直观的定义可以将程序的顺序定义为输入大小和执行时间之间的关系。
链接地址: http://www.djcxy.com/p/39695.html