数据结构(第二版,C语言描述)严蔚敏编著 第一章绪论中的错误

王朝c/c++·作者佚名  2006-01-10
窄屏简体版  字體: |||超大  

课本P16关于冒泡排序:

void bubble_sort(int a[ ], int n){

//将a中整数序列重新排序成自小至大有序的整数序列

for(i = n - 1, change = TRUE; i > 1 && change; --i){ //应为i > 0

change = FALSE;

for(j = 0; j < i; ++j)

if(a[j] < a[j + 1]){ a[j] 互换 a[j + 1]; change = TRUE }

}

}//bubble_sort

我是在计算语句频度的时候发现的:

2 + 3 + 4 +..... + (n-1) = (n+1)(n-2)/2,与课本结果不一致

上机测试(注意:测试数组中的数为逆序),结果:第一个数比第二个数大

应该改为i > 0:

1 + 2 + 3 +.....+ (n-1),利用等差数列公式计算后得到:n(n-1)/2

(在 1 + 2 + 3 + .....+ (n-1)最前面加0便于利用公式计算)

附:时间复杂度的计算方法:

for(i = 0 ; i < n; i++)

for(j = 0; j < n; j++)

x++;

基本操作为:x++;它执行的次数(语句频度)为:n个n相加的和,即n + n + .... + n = n*n

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有  導航