试题出自试卷《2011年下半年软件设计师考试上午真题（专业解析+参考答案）》

问题1选项
A.
B.
C.
D.

A

时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精确计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下：
如果存在两个常数c和m，对于所有的n，当n≥m时有f(n)≤cg(n)，则有f(n)=O(g(n))。也就是说，随着n的增大，f(n)渐进地不大于g(n)。例如，一个程序的实际执行时间为T(n)=3n³+2n²+n，则T(n)=O(n³)。
在本题中，根据题目的描述，我们可以知道，遍历完整个数组中的元素，和修改数组中各元素的值都需要时间n，因此是2n，那么该算法的时间复杂度为O(n)。
空间复杂度是指程序运行从开始到结束所需的辅助存储量，在本题中，只需要辅助存储量来存储统计的元素个数，因此其空间复杂度为O(1)。