2. 从业资格
  3. 对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计A中-

对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计A中-

题库2022-08-02  46
问题 对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计A中-1、0和1的个数，设分别为n1、n2和n3，然后将A中的前n1个元素赋值为-1，第n1+1到nl+n2个元素赋值为0，最后n3个元素赋值为1。该算法的时间复杂度和空间复杂度分别为（　　）。
选项
答案 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)=3n3+2n2+n，则T(n)=O(n3)。
在本题中，根据题目的描述，我们可以知道，遍历完整个数组中的元素，和修改数组中各元素的值都需要时间n，因此是2n，那么该算法的时间复杂度为O(n)。
空间复杂度是指程序运行从开始到结束所需的辅助存储量，在本题中，只需要辅助存储量来存储统计的元素个数，因此其空间复杂度为O(1)。
转载请注明原文地址:https://tihaiku.com/congyezige/2409965.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)