关于渐进时间复杂度的问题在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为?习题的答案是0(1),不知道对不对哦.还有渐进时间复杂度怎么算?如果该成:在一个长度为n的顺序

Question

关于渐进时间复杂度的问题
在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为?
习题的答案是0(1),不知道对不对哦.
还有渐进时间复杂度怎么算?
如果该成:
在一个长度为n的顺序表的表尾插入一个新元素的时间复杂度为?是不是0(n).

Answer 1

在一个长度为n的顺序表的表尾插入一个新元素的时间复杂度为?是不是0(n).
你这个改法和题目一个意思。。。 渐进时间复杂度简称时间复杂度。。。。
答案是对的，就是O(1)，代表是个常量级（因为是在表尾插入的，顺序表读取表尾元素是个常量级操作，插入操作无需移动因此也是个常量级操作）。
渐进时间复杂度怎么算？
写出程序或伪代码，如果外层没有循环，就是O(1)，有一层循环，就是O(n)，有两层就是O(n^2)。。。依次类推。。（其实这个是错的，不过如果是要应付等考什么的，这个方法做出的答案绝对是正确的！）
比如：
x = 1; 这个的频度就是O(1)；
for( i = 0; i < n; ++i )
x = 1; x = 1;这句的频度就是O(n)；
for( i = 0; i < n; ++i )
for( j = 0; j < n; ++j )
x = 1; x = 1;这句的频度就是O(n^2)；
时间复杂度等于一个算法中原操作执行的语句频度，所以上面三个例子的时间复杂度分别为O(1),O(n),O(n^2)；
其他的时间复杂度比如O(nlogn)，一般不会要你求的，最多记住有些算法，比如快速排序、堆排序等，它的时间复杂度是O(nlogn)。
其实正确的时间复杂度算法就是算出该算法中原操作执行的语句频度。原操作的语句频度算法是算出它执行的次数，取最高数量级（非严格表述）。
想知道准确严格的时间复杂度求法，可以参考《算法导论》第一部分第三章---函数增长。