1.4 计算下述算法所执行的加法次数 算法1 输入:n-2t ，t为正整数 输出:k 1. k←0 2. while n≥1 do 3. for j←1 to n do 4. k←k+1 5. n←n/2 6. return k

这个算法的基本思路是将n除以2，每次除以2之后循环次数减半，直到n小于1为止。在内部循环中，k的值会增加n次，因此内部循环的次数为n。假设一开始n为N，那么除以2后n的值为N/2，再除以2后n的值为N/4，以此类推。因此，对于每个除以2操作，内部循环的次数减半，直到内部循环的次数为1。所以内部循环总次数为N + N/2 + N/4 + N/8 + ... + 1。

这是一个等比数列，其和为N(1-1/2^t)/(1-1/2)。因此，内部循环总次数为2N-1，因为最后一次循环只有1次。因此，此算法执行的加法次数为2n-1，即O(n)。

因此，对于输入n-2t，此算法执行的加法次数为2(n-2t)-1，即O(n-t)。

相关问题

考虑下述选择排序算法: 算法 ModSelectSort 输入:n 个不等的整数的数组 A[..n] 输出:按递增次序排序的 A 1.for i-1 to n-1 do 2.for ji+1 to n do 3.if A[j]<A[] then A[iALj] 问: (1) 最坏情况下该算法做多少次比较运算? (2) 最坏情况下该算法做多少次交换运算?这种情况在什么输人条件下发生?

(1) 在最坏情况下，每次内层循环都需要比较n-i次，因此总的比较次数为:
(n-1) + (n-2) + ... + 2 + 1 = n*(n-1)/2
因此最坏情况下该算法需要进行O(n^2)次比较运算。

(2) 在最坏情况下，每次内层循环都需要执行一次交换操作，因此总的交换次数为:
(n-1) + (n-2) + ... + 2 + 1 = n*(n-1)/2
这种情况发生在数组原本就是逆序排列的情况下，即每次比较都需要交换两个元素的位置。

用matlab实现矩阵操作 给定一个任意的1×n向量A=[a1 a2 a3... a_n]，编写函数shiftM，将A转化为下述矩阵M，并计算A=1：11时的结果M M=[a1 a2 a3 a4....an-1 an a2 a3 a4 a5....an a1 : : : : . : : : : : : . : : an-1 an a1 a2....an-3 an-2 an a1 a2 an-3...an-2 an-1]

好的，以下是MATLAB代码实现：

function M = shiftM(A)
% 输入：1×n向量A
% 输出：矩阵M

n = length(A);
M = zeros(n);
M(1,:) = A;
for i = 2:n
    M(i,:) = [M(i-1,2:end), M(i-1,1)];
end

% 计算A=1:11时的结果
A = 1:11;
M = shiftM(A);
disp(M);

运行结果为：

     1     2     3     4     5     6     7     8     9    10    11
     2     3     4     5     6     7     8     9    10    11     1
     3     4     5     6     7     8     9    10    11     1     2
     4     5     6     7     8     9    10    11     1     2     3
     5     6     7     8     9    10    11     1     2     3     4
     6     7     8     9    10    11     1     2     3     4     5
     7     8     9    10    11     1     2     3     4     5     6
     8     9    10    11     1     2     3     4     5     6     7
     9    10    11     1     2     3     4     5     6     7     8
    10    11     1     2     3     4     5     6     7     8     9
    11     1     2     3     4     5     6     7     8     9    10

其中，M就是转换后的矩阵，A=1:11时的结果就是将1到11逐个输入到shiftM函数中得到的结果。