试说明，即便计入向量扩容所需的时间，就分摊意义而言，GraphMatrix::insert（v)算法的时间复杂度依然不超过o（n)。

答案

查看答案

发布时间：2022-09-15

更多“试说明，即便计入向量扩容所需的时间，就分摊意义而言，GraphMatrix::insert（v)算法的时间复杂度依然不超过o（n)。”相关的问题

第1题

对于几乎有序的向量，如教材代码2.26（60页)和代码2.27（60页)所示的起泡排序算法，都显得效率不足

对于几乎有序的向量，如教材代码2.26(60页)和代码2.27(60页)所示的起泡排序算法，都显得效率不足，比如，即便乱序元素仅限于A[0，√n)区间，最坏情况下仍需调用bubble()做Ω(√n)次调用，共做Ω(n)次交换操作和Ω(n^3/2)次比较操作，因此累计运行Ω(n^3/2)时间。

a)试改进原算法，使之在上述情况下仅需o(n)时间;

b)继续改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于A[n-√n，n)区间;

c)综合以上改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于任意的A[m，m+√n]区间。

点击查看答案

第2题

随着问题输入规模的不断扩大，同一算法所需的计算时间通常都呈单调递增趋势，但情况亦并非总是如此。试举实例说明，随着输入规模的扩大，同一算法所需的计算时间可能上下波动。

点击查看答案

第3题

经过至多（n-1)+（n-2)=2n-3次比较，不难从任何存有n个整数的向量中找出最大者和次大者，试改进这一算法，使所需的比较次数（即便在最坏情况下)也不超过[3n/2]-2。

点击查看答案

第4题

教材2.6节针对有序向量介绍的各种查找算法，落实减而治之策略的形式均大同小异，反复地“猜测”某

一元素S[mi]，并通过将目标元素与之比较的结果，确定查找范围收缩的方向，然而在某些特殊的场合，沿前、后两个方向深入的代价并不对称，甚至其中之一只允许常数次。

比如，在仅能使用直尺的情况下，可通过反复实验，用鸡蛋刚能摔碎的下落高度(比如精确到毫米)来度量蛋壳的硬度。尽管可以假定在破裂之前蛋壳的硬度保持不变，但毕竟破裂是不可逆的。故若仅有一枚鸡蛋，则我们不得不从0开始，以1毫米为单位逐步增加下落的高度，若蛋壳的硬度不超过n毫米，则需要进行o(n)次实验。就效率而言，这等价于退化到无序向量的顺序查找。

a)若你拥有两枚鸡蛋(假定它们硬度完全相同)，所需实验可减少到多少次？试给出对应的算法;

b)进一步地，如果你拥有三枚鸡蛋呢？

c)一般地，如果共有d枚鸡蛋可用呢？

点击查看答案

第5题

考查教材40页代码2.11中的无序向量插入算法insert（r，e)。试证明，若插入位置r等概率分布，则该算法的平均时间复杂度为0（n)，n为向量的规模。

点击查看答案

第6题

在给定了空间直角坐标系的三维空间中，所有自原点引出的向量添上零向量构成一个三维线性空间R卐

在给定了空间直角坐标系的三维空间中，所有自原点引出的向量添上零向量构成一个三维线性空间R³。

1)问所有终点都在一个平面上的向量是否为子空间？

2)设有过原点的三条直线，这三条直线上的全部向量分别成为三个子空间L₁，L₂，L₃。问L₁+L₂，L₁+L₂+L₃能构成哪些类型的子空间，试全部列举出来。