Question

数据结构算法复杂度问题

【例3．9】交换i和j的内容。
Temp=i;
i=j;
j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。
如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

如何理解上面一段话，上面代码明明就没有规模，怎么谈得上“与问题规模n无关”呢，我让它执行100次，不就有规模了吗

Answer 1

************我说说**********************
"如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。"

不理解吗??

是这样的,算法不是说总共有多少单条语言,
Temp=i;
i=j;
j=temp;
总共由3条语言,每条的频度均为1,每条的频度可认为都是O(1),那么T(n)=O(1)+O(1)+O(1)=O(1)。

又看下面4条语句:
scanf("%d",&n);
i=n;
for(i=0,i<n;i++) i= i*1; (这也只算是一句)
for(i=0,i<n*n;i++) i=i*1;(同上)
前两条频度均为1;
后两条分别频度为 n和n*n
那么总频度均为
O(1)+O(1)+O(n)+O(n*n)=O(n*n)
(这个式子左边为什么等于右边的O(n*n)?? 别问我,我懒得说了,这不是C/C++问题了,这是数学问题了,不懂自己去看高等数学.)

语句再多,总是有限的,而最多的还是某个单个语句的频度最花时间了.

单条语句,如 for(){for(){for(){}}}和while(1){for(){}}等等象这样的,都可算是一条,自己算吧

一条语句可能执行n多年都不完,如:f(i=0;;i++); 除非你终止它!!!

Answer 2

上面的语句规模应该是3（n的值），规模就是程序运行的复杂度，有空间和时间的，这里主要是时间的。这里的规模就是n(时间复杂度)的大小。不管n多大，都可以用规模来形象的表示。
但是n只要是个常数，不管n多大，复杂度都是O(1).
但是要是循环就不一样了：
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
x=2;
}
那么复杂度就是O(m*n)了。

Answer 3

************我说说**********************
"如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。"
不理解吗??
是这样的,算法不是说总共有多少单条语言,
Temp=i;
i=j;
j=temp;
总共由3条语言,每条的频度均为1,每条的频度可认为都是O(1),那么T(n)=O(1)+O(1)+O(1)=O(1)。
又看下面4条语句:
scanf("%d",&n);
i=n;
for(i=0,i<n;i++)
i=
i*1;
(这也只算是一句)
for(i=0,i<n*n;i++)
i=i*1;(同上)
前两条频度均为1;
后两条分别频度为
n和n*n
那么总频度均为
O(1)+O(1)+O(n)+O(n*n)=O(n*n)
(这个式子左边为什么等于右边的O(n*n)??
别问我,我懒得说了,这不是C/C++问题了,这是数学问题了,不懂自己去看高等数学.)
语句再多,总是有限的,而最多的还是某个单个语句的频度最花时间了.
单条语句,如
for(){for(){for(){}}}和while(1){for(){}}等等象这样的,都可算是一条,自己算吧
一条语句可能执行n多年都不完,如:f(i=0;;i++);
除非你终止它!!!