快速排序方法的时间复杂度为O(n^2）=n(n-1)/2.

Question

这里面的O（）这个函数是什么意思啊？还有好多写时间复杂度的，O(n)什么的，都是什么意思啊，怎么得出来的这个啊？都搞糊涂了。

Answer 1

1）对于你的问题简单解释如下：
理论计算机研究中，衡量算法一般从两个方面分析：时间复杂度和空间复杂度。空间复杂度跟时间复杂度是类似的，下面简单解释一下时间复杂度：对于一个数据规模为n的问题，解决该问题的算法所用时间可以用含有n的函数T(n)来表示。对于绝大多数情况，我们只需要了解算法的一般性能而不考虑细节，也就是说，我们只关心函数T(n)的表达式的形式，而不关心表达式的常数系数等与数据规模没有关系的量值。对于函数T(n)，我们又进一步将它简化为O(n)，即只考虑算法平均运行时间的“瓶颈”，也就是T(n)表达式中，关于变量n增长最快的哪一项。比如下面的代码：
for(int i=1; i<=n*2; i++)
for(int j=1; j<=n; j++)
// do something here
那么这个算法的时间复杂度就是O(n^2)，因为它有两层循环，每层循环的数据规模都是n。注意第一层循环（外循环）要迭代n*2次，则实际上T(n)=2*n*n，而对于O(n)来说，我们忽略了常数2，只保留了n^2。这就是大O记法的一个概括，并不精确。
对于时间复杂度的更精确、深入的解释，可以自己查阅《算法导论》第一章。

2）更正你的问题：快速排序算法的时间复杂度应该为O(n lg n)。注意三种时间复杂度符号表示的不同意义！英文字母O代表的是平均运行时间，因此对于快速排序来说应该是O(n lg n)。而使用下界函数Omega或者上界函数Theta则分别表示算法运行的最快和最慢时间。对于未使用随机化的快速排序，理论上可以证明，存在某一方法构造出一组数据使快速排序“退化”成平方复杂度算法即Theta(n^2)。但是对于其O(n)表示法应该为O(n^2)。

Answer 2

n 趋于无穷大时无穷大的阶数。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。本回答被网友采纳

Answer 3

学数据结构必学的。