登录 |  注册 |  繁體中文


排序算法 时间复杂度

分类: 随笔 颜色:橙色 默认  字号: 阅读(260) | 评论(0)

排序算法,时间复杂度如下

下面用冒泡排序,解释时间复杂度的意思

冒泡排序是一种用时间换空间的排序方法,每一次比较都需要进行交换运算。举个例子来说,一个数列 5 4 3 2 1 进行冒泡升序排列,第一次大循环从第一个数(5)开始到倒数第二个数(2)结束,比较过程:先比较5和4,4比5小,交换位置变成4 5 3 2 1;比较5和3,3比5小,交换位置变成4 3 5 2 1……最后比较5和1,1比5小,交换位置变成4 3 2 1 5。这时候共进行了4次比较交换运算,最后1个数变成了数列最大数。 第二次大循环从第一个数(4)开始到倒数第三个数(2)结束。进行3次比较交换运算。 …… 所以总的比较次数为 4 + 3 + 2 + 1 = 10次

对于n位的数列则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2,这就得到了最大的比较次数 而O(N^2)表示的是复杂度的数量级

举个例子来说,如果n = 10000,那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2,相对10000^2来说,10000小的可以忽略不计了,所以总计算次数约为0.5 * N^2。用O(N^2)就表示了其数量级(忽略前面系数0.5)




姓 名: *
邮 箱:
内 容: *
验证码: 点击刷新 *   

回到顶部