开封市建设局网站网站开发完成后如何发布

开封市建设局网站,网站开发完成后如何发布,网站编程设计方向,无锡科技网站建设2-1 #xff08;在归并排序中对小数组采用插入排序#xff09;虽然归并排序的最坏情况运行时间为 Θ(n lg n)#xff0c;而插入排序的最坏情况运行时间为 Θ(n)#xff0c;但是插入排序中的常量因子可能使得它在 n 较小时#xff0c;在许多机器上实际运行得更快。因此在归并排序中对小数组采用插入排序虽然归并排序的最坏情况运行时间为 Θ(n lg n)而插入排序的最坏情况运行时间为 Θ(n²)但是插入排序中的常量因子可能使得它在 n 较小时在许多机器上实际运行得更快。因此在归并排序中当子问题变得足够小时采用插入排序来使递归的叶变量是有意义的。考虑对归并排序的一种修改其中使用插入排序来排序长度为 k 的 n/k 个子表然后使用标准的合并机制来合并这些子表这里 k 是一个特定的值。a. 证明插入排序最坏情况可以在 Θ(nk) 时间内排序每个长度为 k 的 n/k 个子表。b. 表明在最坏情况下如何在 Θ(n lg (n/k)) 时间内合并这些子表。c. 假定修改后的算法的最坏情况运行时间为 Θ(nkn lg (n/k))要使修改后的算法与标准的归并排序具有相同的运行时间作为 n 的一个函数借助 Θ 记号k 的最大值是什么d. 在实践中我们应该如何选择 k我的答案与思考证明a长度为 k 的 n/k 个子表。每个子表在最坏情况下O(k^2)共有n/k 个子表所以总时间复杂度为O(k^2*n/k) O(kn) O(nk)证明b在每一层的元素个数都为nn/k * k 2合并需要遍历每个元素并比较子表时间为常数O(1)因此每一层的时间复杂度为O(n)而一共有lg(n/k)层因此需要O(n*lg(n/k))时间合并。证明cΘ(nkn lg (n/k))O(nlgn)klg(n/k) lg nk lgn -lgk lgnk lgkk1时1 !0k2时2!1k4时4!2…d 尽量选中最大的kDeepseek分析a.证明插入排序最坏情况可以在 Θ(nk) 时间内排序每个长度为 k 的 n/k 个子表。每个子表长度为 k插入排序最坏情况时间为 Θ(k²)。共有 n/k 个子表因此总时间为 Θ(k² · n/k) Θ(nk)。b.表明在最坏情况下如何在 Θ(n lg (n/k)) 时间内合并这些子表。合并过程使用标准的归并排序合并机制。初始时有 n/k 个已排序的子表每个长度为 k。合并这些子表类似于归并排序的递归树树高为 lg(n/k)因为每次合并子表数量减半每层需要处理所有 n 个元素比较和移动因此总时间为 Θ(n lg(n/k))。c.要使修改后的算法与标准归并排序具有相同的运行时间 Θ(n lg n)需满足 Θ(nk n lg(n/k)) Θ(n lg n)。两边除以 n 得k lg(n/k) Θ(lg n)。进一步分解k lg n - lg k Θ(lg n) ⇒ k - lg k Θ(0)。这意味着 k 必须满足 k O(lg n)且 lg k o(lg n)即 k 的增长慢于多项式增长。当 k Θ(lg n) 时nk Θ(n lg n)且 n lg(n/k) Θ(n lg n)总时间为 Θ(n lg n)。若 k 比 lg n 增长更快如 k (lg n)²则 nk 项占主导总时间超过 Θ(n lg n)。因此k 的最大值为 Θ(lg n)。d.在实践中k 的选择应通过实验确定在目标机器上测试不同 k 值下排序的性能选择使运行时间最小的 k。通常 k 取值在 10 到 20 之间。2-2冒泡排序的正确性 冒泡排序是一种流行但低效的排序算法它的作用是反复交换相邻的未按次序排列的元素。BUBBLESORT(A)1 for i 1 to A.length - 12 for j A.length downto i 13 if A[j] A[j - 1]4 exchange A[j] with A[j - 1]a. 假设 A′ 表示 BUBBLESORT(A) 的输出。为了证明 BUBBLESORT 正确我们必须证明它将终止并且有A′[1] ≤ A′[2] ≤ ⋯ ≤ A′[n] (2.3)其中 n A.length。为了证明 BUBBLESORT 确实完成了排序我们还需要证明什么下面两部分将证明不等式(2.3)。b. 为第 2~4 行的 for 循环精确地说明一个循环不变式并证明该循环不变式成立。你的证明应该使用本章中给出的循环不变式证明的结构。c. 使用(b)部分证明的循环不变式的终止条件为第 1~4 行的 for 循环说明一个循环不变式该不变式将使你能证明不等式(2.3)。你的证明应该使用本章中给出的循环不变式证明的结构。d. 冒泡排序的最坏情况运行时间是多少与插入排序的运行时间相比其性能如何我的答案与思考a.冒泡排序是通过一直比较相邻元素如果满足条件就将其放到正确的位置如要求后面元素小于前面元素就会交互位置每次循环会利用这个机制如果遇到数组中的最小值会一直交互位置直到停止位置因此可以通过两次循环外层循环是确定停止位置内层循环是将停止位置后面的元素进行相邻元素交互最终将最小值带过来。证明每次外层循环都能将最小值放在最前面。b.循环不变式为A[j]为A[j..n]的最小值。初始jnA[j..n]中只有一个元素A[j]确实是A[j..n]中的最小值满足。每次循环前通过一直交互顺序如果有一个值为A[j..n]中的最小值那它就一直满足条件一直被搬运到A[j]的位置所以满足。终止j为中i1将A[j..n]中最小值搬运到A[i1]位置满足条件。c.根据b中循环不等式的终止条件所以第 1~4 行的循环不等式为A[i]为A[1..i]中的最大值。初始i1A[1..i]中只有A[1]一个元素满足为最大值的条件。每次循环前经过前一次循环已经将当前A[i-1..n]中最小值搬运到A[i-1]中了因此A[i-1]为A[i-1..n]中最小值A[1..i-1]中最大值满足。终止已排好序in-1满足A[n-1]为A[1..n-1]中的最大值。d.第一次外层循环内层循环需要n次…最后一次需要2次。共有2345…n次(n-1)(n2)/2因此为O(n^2)与插入排序相同。Deepseek分析a.除了证明输出满足 A′[1] ≤ A′[2] ≤ ⋯ ≤ A′[n]还需证明输出序列是输入序列的一个排列即元素相同仅顺序改变。b.内层循环2~4行的循环不变式在每次迭代开始时A[j] 是子数组 A[j..n] 中的最小元素。证明初始化j A.length子数组 A[j..n] 仅含 A[j]显然成立。保持假设迭代前 A[j] 是 A[j..n] 的最小元素。比较 A[j] 和 A[j-1]若 A[j] A[j-1]则交换使得 A[j-1] 变为原来 A[j] 和 A[j-1] 中的较小值。由于原来 A[j] 是 A[j..n] 的最小值交换后 A[j-1] 比原 A[j-1] 小且比 A[j..n] 中其他元素小因为原 A[j] 最小。然后 j 减 1新的 A[j]即原 A[j-1]可能不是 A[j..n] 的最小值但注意下一次迭代将比较新的 A[j] 和 A[j-1]继续将最小值前移。实际上内层循环的目标是在结束时使 A[i] 成为 A[i..n] 的最小值该不变式需配合外层循环理解。终止j i1迭代后 A[i] 成为 A[i..n] 的最小值。c.外层循环1~4行的循环不变式在每次迭代开始时子数组 A[1..i-1] 包含原数组中最小的 i-1 个元素且已按非降序排列。证明初始化i 1A[1..0] 为空成立。保持假设迭代前 A[1..i-1] 包含最小的 i-1 个元素且已排序。内层循环结束后A[i] 是 A[i..n] 的最小元素因此 A[i] 大于等于 A[1..i-1] 中的所有元素且小于等于 A[i1..n] 中的所有元素。故 A[1..i] 包含最小的 i 个元素且已排序。终止i A.lengthA[1..n] 包含全部元素且已排序。d.冒泡排序的最坏情况运行时间为 Θ(n²)与插入排序相同。但实际中冒泡排序通常更慢因为其交换操作更多。2-3霍纳Horner规则的正确性 给定系数 a₀, a₁, ⋯, aₙ 和 x 的值代码片段1 y 02 for i n downto 03 y aᵢ x·y实现了用于求值多项式P(x) ∑{k0}^{n} a_k x^k a₀ x(a₁ x(a₂ ⋯ x(a{n-1} x a_n)⋯))的霍纳规则。我的答案与思考a. 借助 Θ 记号实现霍纳规则的以上代码片段的运行时间是多少一共是n次每次内部循环是常数时间操作因此时间复杂度为O(n)b. 编写伪代码来实现朴素的多项式求值算法该算法从头开始计算多项式的每个项。该算法的运行时间是多少与霍纳规则相比其性能如何int polynomial_evaluation(std::vectorint A, int x) { int sum 0; int v 0; for (int i 0; i A.size(); i) { v 1; if (i ! 0) { v x; for (int j 0; j i - 1; j) { v * x; } } sum A[i] * v; } return sum; }一共n次循环内部是a次运行如果n大于2时112345..n(n2)(n-2)/2 2n^2-2On^2比霍纳规则效率低的多c. 考虑以下循环不变式在第 23 行 for 循环每次迭代的开始有y ∑{k0}^{n-(i1)} a{ki1} x^k把没有项的和式解释为等于 0。遵照本章中给出的循环不变式证明的结构使用该循环不变式来证明终止时有y ∑_{k0}^{n} a_k x^k起始iny0正确。每次循环开始时ya(i1)a(i2)x….a(n)x^n-(i1)正确。终止i0ya1x^1….akx^k正确。d. 最后证明上面给出的代码片段将正确地求由系数 a₀, a₁, ⋯, aₙ 刻画的多项式的值。空。Deepseek分析a.运行时间为 Θ(n)。循环迭代 n1 次每次执行常数时间操作。b.朴素多项式求值算法伪代码NAIVE-POLY-EVAL(A, x) 1 y 0 2 for i 0 to n 3 term 1 4 for j 1 to i 5 term term * x 6 y y A[i] * term 7 return y运行时间为 Θ(n²)因为内层循环计算 x^i 需要 i 次乘法。霍纳规则仅需 Θ(n)性能更优。c.循环不变式证明初始化i ny 0右边求和为空定义为 0成立。保持假设迭代开始时 y ∑{k0}^{n-(i1)} a{ki1} x^k。执行 y a_i x·y 后y a_i x·∑{k0}^{n-(i1)} a{ki1} x^k a_i ∑{k0}^{n-(i1)} a{ki1} x^{k1} a_i ∑{k1}^{n-i} a{ki} x^k ∑{k0}^{n-i} a{ki} x^k。i 减 1 后下一次迭代开始时的 i i-1右边求和为 ∑{k0}^{n-(i1)} a{ki1} x^k ∑{k0}^{n-i} a{ki} x^k与上式一致不变式保持。终止i -1此时 y ∑_{k0}^{n} a_k x^k得证。d.根据 c 中的证明代码正确实现了霍纳规则能正确求值多项式。2-4逆序对假设 A[1..n] 是一个有 n 个不同数的数组。若 i j 且 A[i] A[j]则对偶 (i, j) 称为 A 的一个逆序对inversion。我的答案与思考a. 列出数组 (2, 3, 8, 6, 1) 的 5 个逆序对。2131816186b. 由集合 {1, 2, ..., n} 中的元素构成的什么数组具有最多的逆序对它有多少逆序对最多有n-1n-2…1n(n-1)/2个它有0个c. 插入排序的运行时间与输入数组中逆序对的数量之间是什么关系证明你的回答。插入排序的运行时间与数组中逆序对的数量正相关。插入排序中内层循环进入条件有需要保证A[i]A[j]且ij正好和逆序对中的若 i j 且 A[i] A[j] 一样也就是说存在逆序对才能进入内层循环。d. 给出一个确定在 n 个元素的任何排列中逆序对数量的算法最坏情况需要 Θ(n lg n) 时间。提示修改归并排序。void merge(std::vectorint A, int p, int q, int r) { std::vectorint L(A.begin() p, A.begin() q 1); std::vectorint R(A.begin() q 1, A.begin() r 1); int i 0, j 0; for (int k p; k r; k) { if (i L.size()) { A[k] R[j]; j; } else if (j R.size()) { A[k] L[i]; i; } else if (L[i] R[j]) { A[k] L[i]; i; } else { A[k] R[j]; j; } } } void merge_sort(std::vectorintA, int p, int r ) { if (p r) { int q (p r) / 2; merge_sort(A, p, q); merge_sort(A, q 1, r); merge(A, p, q, r); } } int main() { std::vectorint n1 { 5,2,4,7,1,3,2,6 }; auto n2 n1; int n 0; merge_sort(n1, 0, n1.size() - 1); for (int i 0; i n1.size(); i) { if (n1[i] ! n2[i]) { n; } } std::cout n n std::endl; return 0; }时间复杂度O(lgn * n n) O(nlgn)Deepseek分析a.数组 ⟨2, 3, 8, 6, 1⟩ 的逆序对(2,1), (3,1), (8,1), (6,1), (8,6)。共 5 个。b.逆序对最多的数组是严格递减的数组逆序对数为 n(n-1)/2。严格递增的数组逆序对数为 0。c.插入排序的运行时间与逆序对数量成正比。因为插入排序的内层循环每次交换相邻元素恰好消除一个逆序对其他操作为常数时间。若逆序对数量为 I则运行时间为 Θ(n I)。最坏情况 I Θ(n²)运行时间为 Θ(n²)。d.修改归并排序以计数逆序对在合并两个已排序子数组时若从右子数组取出元素则左子数组剩余的所有元素均大于该元素逆序对增加左子数组剩余元素个数。伪代码COUNT-INVERSIONS(A, p, r) 1 if p r 2 q ⌊(p r)/2⌋ 3 left COUNT-INVERSIONS(A, p, q) 4 right COUNT-INVERSIONS(A, q1, r) 5 inv MERGE-INVERSIONS(A, p, q, r) 6 return left right inv MERGE-INVERSIONS(A, p, q, r) 1 n1 q - p 1 2 n2 r - q 3 创建数组 L[1..n1] 和 R[1..n2] 4 for i 1 to n1 5 L[i] A[p i - 1] 6 for j 1 to n2 7 R[j] A[q j] 8 i 1, j 1, k p, inv 0 9 while i ≤ n1 and j ≤ n2 10 if L[i] ≤ R[j] 11 A[k] L[i] 12 i i 1 13 else 14 A[k] R[j] 15 j j 1 16 inv inv (n1 - i 1) // 左子数组剩余元素个数 17 k k 1 18 while i ≤ n1 19 A[k] L[i] 20 i i 1, k k 1 21 while j ≤ n2 22 A[k] R[j] 23 j j 1, k k 1 24 return inv运行时间为 Θ(n lg n)。Deepseek总结你的回答大部分正确但在一些细节上需要完善尤其是循环不变式的证明和逆序对计数的算法。