Question

在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为?

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

Answer 1

课后答案是对的，不过是o（1），不是0（1）。
一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做T(n)=Ο(f(n));
因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度。
本题中，顺序表表尾插入新元素仅需一次计算，且与n的大小无关，故f（n）=1，时间复杂度仍为o（1）。

Answer 2

o（1） 顺序表表尾插入新元素仅需一次计算，且与n的大小无关，故f（n）=1，时间复杂度仍为o（1）。