<算法导论>学习笔记(2)
Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices. 是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。 1. 循环不变式的三
Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.
是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。
1. 循环不变式的三个性质:(循环不变式通常用来证明递归的正确性)
1. 初始化:它在循环的第一轮迭代开始之前,应该是正确的。
2. 保持:如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。
3. 终止:当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。
2. 伪代码中的约定:
1. 书写上的“缩进”表示程序中的分程序(程序块)结构。
2. while,for,repeat 等循环结构和 if,then,else 条件结构与 Pascal 中相同。
3. 符号 "?”表示后面部分是个注释。
4. 多重赋值 i←j←e 是将表达式 e 的值赋给变量 i 和 j;等价于 j←e,再进行赋值 i←j。
5. 变量(如 i,j 和 key 等)是局部给定过程的。
6. 数组元素是通过“数组名[下标]”这样的形式来访问的。
7. 复合数据一般组织成对象,它们是由属性(attribute)和域(field)所组成的。
8. 参数采用按值传递方式:被调用的过程会收到参数的一份副本。
9. 布尔运算符"and”和"or”都是具有短路能力。
3. 算法分析即指对一个算法所需要的资源进行预测。
4. 对于一个算法,一般只考察其最坏情况的运行时间,理由有三:
1. 一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界。
2. 对于某些算法来说,最坏情况出现得还是相当频繁的。
3. 大致上看来,“平均情况”通常和最坏情况一样差。
5. 分治策略:将原问题划分成n个规模较小而结构与原问题相似的子问题;递归地解决这些小问题,然后再合并其结 果,就得到原问题的解。
6. 分治模式在每一层递归上都有三个步骤:
1. 分解(Divde):将原问题分解成一系列子问题;
2. 解决(Conquer):递归地解答各子问题。若子问题足够小,则直接求解; 3. 合并(Combine):将子问题的结果合并成原问题的解。
下面具体介绍几个知识点：
本章通过介绍插入排序和归并排序两种常见的排序算法来说明算法的过程及算法分析，在介绍归并排序算法过程中引入了分治（divide-and-conquer）算法策略。
1、插入排序
输入：n个数（a1,a2,a3,...,an）
输出：输入序列的一个排列（a1',a2',a3',...an'）使得（a1'≤a2'≤a3'≤...≤an'）。
插入排序的基本思想是：将第i个元素插入到前面i-1个已经有序的元素中。具体实现是从第2个元素开始（因为1个元素是有序的），将第2个元素插入到前面的1个元素中，构成两个有序的序列，然后从第3个元素开始，循环操作，直到把第n元素插入到前面n-1个元素中，最终使得n个元素是有序的。该算法设计的方法是增量方法。书中给出了插入排序的为代码，并采用循环不变式证明算法的正确性。我采用C语言实插入排序，完整程序如下：
void insert_sort(int *datas,int length)
{
int i,j;
int key,tmp;
//判断参数是否合法
if(NULL == datas || 0==length)
{
printf("Check datas or length.\n");
exit(1);
}
//数组下标是从0开始的，从第二个元素（对应下标1）开始向前插入
for(j=1;j<length key="datas[j];" i="j-1;" while>=0 && datas[i] > key)
{
/×tmp = datas[i+1];
datas[i+1] = datas[i];
datas[i] = tmp;×/ 这个过程不需要进行交换，因为要插入的值保存在key中，没有被覆盖掉，在此感谢”两生花“指出问题所在
datas[i+1] = datas[i];
i--; //向前移动
}
datas[i+1] = key; //最终确定待插入元素的位置
}
}</length>
插入排序算法的分析
算法分析是对一个算法所需的资源进行预测，资源是指希望测度的计算时间。插入排序过程的时间与输入相关的。插入排序的最好情况是输入数组开始时候就是满足要求的排好序的，时间代价为θ(n)，最坏情况下，输入数组是按逆序排序的，时间代价为θ(n^2)。
2、归并排序
归并排序采用了算法设计中的分治法，分治法的思想是将原问题分解成n个规模较小而结构与原问题相似的小问题，递归的解决这些子问题，然后再去合并其结果，得到原问题的解。分治模式在每一层递归上有三个步骤：
分解（divide）：将原问题分解成一系列子问题。
解决（conquer）：递归地解答各子问题，若子问题足够小，则直接求解。
合并（combine）：将子问题的结果合并成原问题的解。
归并排序（merge sort）算法按照分治模式，操作如下：
分解：将n个元素分解成各含n/2个元素的子序列
解决：用合并排序法对两个序列递归地排序
合并：合并两个已排序的子序列以得到排序结果
在对子序列排序时，长度为1时递归结束，单个元素被视为已排序好的。归并排序的关键步骤在于合并步骤中的合并两个已经有序的子序列，引入了一个辅助过程，merge(A,p,q,r)，将已经有序的子数组A[p...q]和A[q+1...r]合并成为有序的A[p...r]。书中给出了采用哨兵实现merge的伪代码，课后习题要求不使用哨兵实现merge过程。在这个两种方法中都需要引入额外的辅助空间，用来存放即将合并的有序子数组，总的空间大小为n。现在用C语言完整实现这两种方法，程序如下：
//采用哨兵实现merge
#define MAXLIMIT 65535
void merge(int *datas,int p,int q,int r)
{
int n1 = q-p+1; //第一个有序子数组元素个数
int n2 = r-q; //第二个有序子数组元素个数
int *left = (int*)malloc(sizeof(int)*(n1+1));
int *right = (int*)malloc(sizeof(int)*(n2+1));
int i,j,k;
//将子数组复制到临时辅助空间
for(i=0;i<n1 left datas for right maxlimit i="0;" j="0;" if else free>不采用哨兵实现，需要考虑两个子数组在合并的过程中哪一个先合并结束，剩下的那个子数组剩下部分复制到数组中，程序实现如下：<br>
<pre class="brush:php;toolbar:false">int merge(int *datas,int p,int q,int r)
{
int n1 = q-p+1;
int n2 = r-q;
int *left = (int*)malloc(sizeof(int)*(n1+1));
int *right = (int*)malloc(sizeof(int)*(n2+1));
int i,j,k;
memcpy(left,datas+p,n1*sizeof(int));
memcpy(right,datas+q+1,n2*sizeof(int));
i = 0;
j = 0;
for(k=p;k<br>
<p>
merge过程的运行时间是θ(n)，现将merge过程作为归并排序中的一个子程序使用，merge_sort(A,p,r),对数组A[p...r]进行排序，实例分析如下图所示：<br>
</p>
<p>
<img src="/static/imghw/default1.png" data-src="pic/20151007/rcq4ovdyk4j.png" class="lazy" alt="<算法导论>学习笔记(2)" ><br>
</p>
<p>
<br>
</p>
<p>
C语言实现如下：<br>
</p>
<pre class="brush:php;toolbar:false">void merge_sort(int *datas,int p,int r)
{
int q;
if(p <br>
归并排序算法分析：<br>
<br>
算法中含有对其自身的递归调用，其运行时间可以用一个递归方程（或递归式）来表示。归并排序算法分析采用递归树进行，递归树的层数为lgn+1，每一层的时间代价是cn，整棵树的代价是cn(lgn+1)=cnlgn+cn，忽略低阶和常量c，得到结果为θ(nlg n)。<br>
<p>
<br>
</p>
<p>
<br>
</p>
<p><strong><em>练习</em></strong></p>
<p><strong>2.1-1：以图2-2为模型，说明INSERTION-SORT在数组A=上的执行过程。</strong></p>
<p>
</p>|
31 |
41 |
59 |
26 |
41 |
58 |
|
31 |
41 |
59 |
26 |
41 |
58 |
|
31 |
41 |
59 |
26 |
41 |
58 |
|
26 |
31 |
41 |
59 |
41 |
58 |
|
26 |
31 |
41 |
41 |
59 |
58 |
|
26 |
31 |
41 |
41 |
58 |
59 |
2.1-2：重写过程INSERTION-SORT，使之按非升序（而不是按非降序）排序。
INSERTION-SORT(A)
1 for j←2 to length[A]
2 do key←A[j]
3 //Insert A[j] into the sorted sequence A[1..j-1]
4 i←j-1
5 while and A[i]
6 do A[i+1] ← A[i]
7 i←i-1
7 A[i+1] ← key
2.1-3：考虑下面的查找问题：
输入：一列数A=
输出：下标i，使得v=A[i]，或者当v不在A中出现时为NIL。
写出针对这个问题的现行查找的伪代码，它顺序地扫描整个序列以查找v。利用循环不变式证明算法的正确性。确保所给出的循环不变式满足三个必要的性质。
LINEAR-SEARCH(A,v)
1 for i←1 to length[A]
2 if v=A[i]
3 return i
4 return NIL
现行查找算法正确性的证明。
初始化： i=1，子数组为A[1..i]，只有一个元素A[1],如果v=A[1]就返回1,否则返回NIL，算法显然是正确的。
保持：若算法对数组A[1..i]正确，则在数组增加一个元素A[i+1]时，只需要多作一次比较，因此显然对A[1..i+1]也正确。
终止：算法如果在非最坏情况下定能返回一个值此时查找成功，如果n次查找（遍历了所有的数）都没有成功，则返回NIL。算法在有限次查找后肯定能够给出一个返回值，要么说明查找成功并给出下标，要么说明无此值。因此算法正确。
该算法用C#实现的代码：
public static int LinearSearch
{
for (int i = 0; i
if (Input[i].Equals(v))
return i;
return -1;
}
2.1-4：有两个各存放在数组A和B中的n位二进制整数，考虑它们的相加问题。两个整数的和以二进制形式存放在具有(n+1)个元素的数组C中。请给出这个问题的形式化描述，并写出伪代码。
A存放了一个二进制n位整数的各位数值，B存放了另一个同样是二进制n位整数的各位上的数值，现在通过二进制的加法对这两个数进行计算，结果以二进制形式把各位上的数值存放在数组C（n+1位）中。
BINARY-ADD(A,B,C)
1 flag← 0
2 for j←1 to n
3 do key←A[j]+B[j]+flag
4 C[j] ← key mod 2
5 if key←1
6 flag←1
7 if flag=1
8 C[n+1] ← 1
1.RAM(Random-Access Machine)模型分析通常能够很好地预测实际计算机上的性能，RAM计算模型中，指令一条接一条地执行，没有并发操作。RAM模型中包含了真实计算机中常见的指令：算术指令（加法、剑法、乘法、出发、取余、向下取整、向上取整指令）、数据移动指令（装入、存储、复制指令）和控制指令（条件和非条件转移、子程序调用和返回指令）。其中每天指令所需时间都为常量。
RAM模型中的数据类型有整数类型和浮点实数类型。
2.算法的运行时间是指在特定输入时，所执行的基本操作数（或步数）。
插入算法的分析比较简单，但是不是很有用，所以略过。（在解思考题2-1时有具体的实例分析，请参看）
3.一般考察算法的最坏情况运行时间。这样做的理由有三点：
A．一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界。
B．对于某些算法，最坏情况出现的是相当频繁的。
C．大致上来看，“平均情况“通常与最坏情况一样差。
4.如果一个算法的最坏情况运行时间要比另一个算法的低，我们常常就认为它的效率更高。
练习
2.2-1：用Θ形式表示表示函数 /1000- -100n+3
Θ(n^3)
2.2-2:考虑对数组A中的n个数进行排序的问题：首先找出A中的最小元素，并将其与A[1]中的元素进行交换。接着，找出A中的次最小元素，并将其与A[2]中的元素进行交换。对A中头n-1个元素继续这一过程。写出这个算法的伪代码，该算法称为选择排序（selection sort）。对这个算法来说，循环不变式是什么?为什么它仅需要在头n-1个元素上运行，而不是在所有n个元素上运行？以 形式写出选择排序的最佳和最坏情况下的运行时间。
假设函数MIN(A,i,n)从子数组A[i..n]中找出最小值并返回最小值的下标。
SELECTION-SORT(A)
1 for i←1 to n-1
2 j←MIN(A,i,n)
3 exchange A[i]←→ A[j]
选择排序算法正确性的证明
初始化：i=1，从子数组A[1..n]里找到最小值A[j]，并与A[i]互换，此时子数组A[1..i]只有一个元素A[1]，显然是已排序的。
保持：若A[1..i]是已排序子数组。这里显然A[1] A[2] A[3] … A[i]，而A[i+1..n]里最小值也必大于A[i]，找出此最小值与A[i+1]互换并将A[i+1]插入A[1..i]得到子数组A[1..i+1]。A[1..i+1]显然也是已排序的。
终止：当i=n时终止，此时已得到已排序数组A[1..n-1]，而A[n]是经过n-1次比较后剩下的元素，因此A[n]大于A[1..n-1]中任意元素，故数组A[1..n]也即是原数组此时已是已排序的。所以，算法正确。
仅需要在头n-1个元素上运行是因为经过n-1次比较后剩下的是最大元素，其理应排在最后一个位置上，因此可以不必对此元素进行交换位置操作。
由于MIN()函数和SWAP()函数对于任意情况运行时间都相等，故这里最佳和最坏情况下运行时间是一样的。 Θ(n^2)
选择算法的的C#实现：
private static int Min
{
int flag=start;
for (int i = start; i
if (Input[flag].CompareTo(Input[i]) > 0)
flag = i;
return flag;
}
private static void Swap
{
T temp;
temp = a;
a = b;
b = temp;
}
public static T[] SelectionSort
{
for (int i = 0; i
Swap(ref Input[Min(Input, i, Input.Length)],ref Input[i]);
return Input;
}
2.2-3：再次考虑线性查找问题（见练习2.1-3）。在平均情况下，需要检查输入序列中的多少个元素？假定查找的元素是数组中任何一个元素的可能性都是相等的。在最坏情况下又怎么样呢？用Θ相似表示的话，线性查找的平均情况和最坏情况运行时间怎么样？对你的答案加以说明。
平均：n/2次。因为任意一个元素大于、小于查找数的概率一样。
最坏：n次。最后一个元素才是要查找的元素。
用Θ表示都是：Θ(n)
2.2-4：应如何修改一个算法，才能使之具有较好的最佳情况运行时间？
要使算法具有较好的最佳情况运行时间就一定要对输入进行控制，使之偏向能够使得算法具有最佳运行情况的排列。
5.分治法（divide-and-conquer）:有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的问题。这些算法通常采用分治策略：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
容易确定运行时间，是分治算法的有点之一。
6.分治模式在每一层递归上都有三个步骤：
分解（Divide）：将原问题分解成一系列子问题；
解决（Conquer）：递归地解各子问题。若子问题足够小，则直接求解；
合并（Combine）：将子问题的结果合并成原问题的解。
7.合并排序（Merge Sort）算法完全依照了分治模式。
分解：将n个元素分成各含n/2个元素的子序列；
解决：用合并排序法对两个子序列递归地排序；
合并：合并两个已排序的子序列以得到排序结果。
在对子序列排序时，其长度为1时递归结束。单个元素被视为是已排好序的。
合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做合并，引入一个辅助过程MERGE(A,p,q,r)，其中A是个数组，p、q和r是下标，满足 。该过程假设子数组A[p..q]和A[q+1..r]都已排好序，并将他们合并成一个已排好序的子数组代替当前子数组A[p..r]。
MERGE过程的时间代价为Θ(n)，其中n=r-p+1是待合并的元素个数。
MERGE过程:
MERGE(A,p,q,r)
1 n1←q-p+n
2 n2←r-p
3 //create arrays L[1..n1+1] and R[1..n2+1]
4 for i←1 to n1
5 do L[i] ← A[p+i-1]
6 for j←1 to n2
7 do R[j] ← A[q+j]
8 L[ ] ←无穷
9 R[ ] ←无穷
10 i←1
11 j←1
12 for k←p to r
13 do if L[i]
14 then A[k] ← L[i]
15 i←i+1
16 else A[k] ← R[j]
17 j←j+1
MERGE过程正确性的证明
初始化：第一轮循环，k=p，i=1，j=1，已排序数组L、R，比较两数组中最小元素L[i]、R[j]，取较小的置于A[p]，此时子数组A[p..p]不仅是已排序的（仅有一个元素），而且是所有待排序元素中最小的。若最小元素是L[i]，取i=i+1，即i指向L中未排入A的所有元素中最小的一个；同理，j之于R数组也是如此。
保持：若A[p..k]是已排序的，由计算方法知，L中i所指、R中j所指及其后任意元素均大于等于A[p..k]中最大元素A[k],当k=k+1，A[k+1]中存入的是L[i]、R[j]中较小的一个，但是仍有A[k]
终止： k=r+1时终止跳出循环，此时，A[p..r]是已排序的，且显有A[p] A[p+1] .. A[r]。此即原待排序子数组，故算法正确。
MERGE-SORT(A,p,r)
1 if p 2 then q← [(p+r)/2] 3 MERGE-SORT(A,p,r) 4 MERGE-SORT(A,q+1,r) 5 MERGE-SORT(A,p,q,r) 算法与二叉树的后序遍历算法（先左子树，然后右子树，最后根）相似。 （第三行、第四行顺序可以互换） 合并排序算法的C#实现代码： public static void MergeSort { int q; if (p
{ q = (p + r) / 2; MergeSort(Input, p, q); MergeSort(Input, q + 1, r); Merge(Input,p,q,r); } } private static void Merge { int n1 = q - p + 1; int n2 = r - q; T[] L = new T[n1]; T[] R = new T[n2]; for (int i = 0; i
L[i] = Input[p + i]; for (int j = 0; j
R[j] = Input[q + 1 + j]; for (int i = 0, j = 0, k = p; k
{ if(i if (L[i].CompareTo(R[j])
{ Input[k] = L[i]; ++i; continue; } else { Input[k] = R[j]; ++j; continue; } if (i >= n1 && j
{ Input[k] = R[j]; ++j; continue; } if (i = n2) { Input[k] = L[i]; ++i; continue; } } } 8.当一个算法中含有对其自身的递归调用时，其运行时间可以用一个递归方程（或递归式）来表示。 合并算法的递归式： n D(n)是分解该问题所用时间，C(n)是合并解的时间；对于合并排序算法，a和b都是2 T(n)在最坏的情况下合并排序n个数的运行时间分析: 当n>1时，将运行时间如下分解： 分解：这一步仅仅算出子数组的中间位置，需要常量时间，因而D(n)=Θ(1) 解决：递归地解为两个规模为n/2的子问题，时间为T(n/2) 合并：含有n个元素的子数组上，MERGE过程的运行时间为C(n) =Θ(n) n=1时,T(n)=Θ(1),n>1时T(n)=2T(n/2)+ Θ(n) 将上式改写： n=1时,T(n)=c,n>1时T(n)=2T(n/2)+ cn 在所构造的递归树中，顶层总代价为cn（n个点的集合）。往下每层总代价不变，第i层的任一节点代价为c(n/2^i)（共2^i个节点总代价仍然是cn）。最底层有n个节点（n*1），每个点代价为c。此树共有lgn+1层，深度为lgn。 因此n层的总代价为：cn*(lgn+1)=cnlgn+cn=Θ(nlgn)
练习 2.3-1：2-4为模型，说明合并排序在输入数组A=上的执行过程。 以文字代替图示 1.(3)(41)→(3,41);(52)(26) →(26,52);(38)(57) →(38,57);(9)(49) →(9,49) 2.(3,41)(26,52) →(3,26,41,52);(38,57)(9,49) →(9,38,49,57) 3.(3,26,41,52)(9,38,49,57) →(3,9,26,38,41,49,52,57) 2.3-2：MERGE过程，使之不适用哨兵元素，而是在一旦数组L或R中的所有元素都被复制回数组A后，就立即停止，再将另一个数组中余下的元素复制回数组A中 MERGE(A,p,q,r) 1 n1←q-p+n 2 n2←r-p 3 //create arrays L[1..n1] and R[1..n2] 4 for i←1 to n1 5 do L[i] ←A[p+i-1] 6 for j←1 to n2 7 do R[j] ← A[q+j] 8 i←1 9 j←1 10 for k←p to r 11 do if i 12 if L[i]
13 A[k] ← L[i] 14 i←i+1 15 continue 16 else A[k] ← R[j] 17 j←j+1 18 continue 19 do if i>=n1 and j 20 A[k] ← R[j] 21 j←j+1 22 continue 23 do if i 24 A[k] ← L[i] 25 i←i+1 26 continue 2.3-3：利用数学归纳法证明：当n是2的整数次幂时，递归式 这个公式比较难贴上来，请大家看PDF。 2.3-4：插入排序可以如下改写成一个递归过程：为排序A[1..n]，先递归地排序A[1..n-1]，然后再将A[n]插入到已排序的数组A[1..n-1]中去。对于插入排序的这一递归版本，为它的运行时间写一个递归式。 首先是INSERTION过程 INSERTION (A,p,r) 1 for j←p to r 2 do key←A[j] 3 i←j-1 4 while i>0 and A[i]>key 5 do A[i+1] ← A[i] 6 i←i-1 7 A[i+1] ← key 插入排序的递归调用算法： RECURSION-INSERTION-SORT(A,p,r) 1 if p 2 r←r-1 3 RECURSION-INSERTION-SORT(A,p,r) 4 INSERTION(A,p,r) 该算法的C#实现代码： public static void RecursionInsertionSort { if (p
{ --r; RecursionInsertionSort(Input, p, r); Insertion(Input,p,r); } } private static void Insertion { T key; int i; for (int j = 1; j
{ key = Input[j]; i = j - 1; for (; i >= 0 && Input[i].CompareTo(key) > 0; i--) Input[i + 1] = Input[i]; Input[i + 1] = key; } } n
2.3-5：回顾一下练习2.1-3中提出的查找问题，注意如果序列A是已排序的，就可以将该序列的中点与v进行比较。根据比较的结果，原序列中有一半就可以不用再做进一步的考虑了。二分查找（binary search）就是一个不断重复这一查找过程的算法，它每次都将序列余下的部分分成两半，并只对其中的一半做进一步的查找。写出二分查找算法的伪代码，可以是迭代的，也可以是递归的。说明二分查找的最坏情况运行时间为什么是Θ(lgn)。 使用递归，先确定一个过程BINARY(A,p,r,v) BINARY(A,p,r,v) 1 for j← p to r 2 if A[j]=v 3 return j 4 return NIL 然后是二分查找的递归过程 BINARY-SEARCH(A,p,r,v) 1 if p=0 and r=0 and A[0]=v 2 return 0 3 if p 4 q←[(p+r)/2] 5 if A[q]> v 6 BINARY-SEARCH(A,p,q,v) 7 return BINARY(A,p,q,v) 8 else BINARY-SEARCH(A,q+1,r,v) 9 return BINARY(A,q+1,r,v) 10 return NIL 该算法的C#实现代码： public static int BinarySearch { int q; if (p == 0 && r == 0 && Input[0].Equals(v)) return 0; if (p
{ q = (p + r) / 2; if (Input[q].CompareTo(v) > 0 ) { BinarySearch(Input, p, q, v); return Binary(Input, p, q, v); } else { BinarySearch(Input, q + 1, r, v); return Binary(Input, q+1, r, v); } } return -1; } private static int Binary { for (int j = p; j
if (Input[j].Equals(v)) return j; return -1; } 由公式N=a^(log a N)得：n*1/(2^(lgn))=1 因经过n次的与中点比较后肯定能找到最后一个点（最坏情况了），如果是返回下标，否则返回NIL，故最坏情况下时间复杂度为 2.3-6：观察一下2.1节中给出的INSERTION-SORT过程，在第5~7行的while循环中，采用了一种线性查找策略，在已排序的子数组A[1..j-1]中（反向）扫描。是否可以改为二分查找策略（见练习2.3-5），来将插入排序的总体最坏情况运行时间改善至Θ(nlgn)？ 首先引入一个二分查找策略（与2.3-5的Binary Search略有不同） BINARY(A,p,r,v) 5 for j←p to r 6 if A[j]> v 7 return j 8 return NIL 然后是二分查找的递归过程 BINARY-SEARCH(A,p,r,v) 10 if p=0 and r=0 and A[0] v 11 return 0 12 if p 13 14 if A[q] v 15 BINARY-SEARCH(A,p,q,v) 16 return BINARY(A,p,q,v) 17 else BINARY-SEARCH(A,q+1,r,v) 18 return BINARY(A,q+1,r,v) 10 return NIL 利用了二分查找策略的插入排序： BINARYINSERTION-SORT(A) 1 for j 2 to length[A] 2 do key A[j] 3 i j-1 4 k BINARY-SEARCH(A,0,i,key) 5 if k!= NIL 6 for s i downto k 7 A[s+1] A[s] 8 A[k] key 此算法的在最坏情况下的运行时间是 该算法的C#实现代码： private static int BinarySearchForInsertionSort { int q; if (p == 0 && r == 0 && Input[0].CompareTo(v)>0) return 0; if (p
{ q = (p + r) / 2; if (Input[q].CompareTo(v) > 0) { BinarySearchForInsertionSort(Input, p, q, v); return BinaryForInsertionSort(Input, p, q, v); } else { BinarySearchForInsertionSort(Input, q+1, r, v); return BinaryForInsertionSort(Input, q+1, r, v); } } return -1; } private static int BinaryForInsertionSort { for (int j = p; j
if (Input[j].CompareTo(v) > 0) return j; return -1; } public static void BinaryInsertionSort { T key; int i, k; for (int j = 1; j
{ key = Input[j]; i = j - 1; k = BinarySearchForInsertionSort(Input, 0, i, key); if (k != -1) { for (int s = i; s>=k ; s--) Input[s + 1] = Input[s]; Input[k] = key; } } } *2.3-7：请给出一个运行时间为Θ(nlgn)的算法，使之能在给定一个由n个整数构成的集合 和另一个整数 时，判断出 中是否存在有两个其和等于 的元素。 利用2.3-5中的BINARY-SEARCH(A,v)和2.3-6中的BINARYINSERTION-SORT(S)算法 ISEXISTSUM(S,x) 1 BINARYINSERTION-SORT(S) 2
핫 AI 도구
Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱
AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.
Undress AI Tool
무료로 이미지를 벗다
Clothoff.io
AI 옷 제거제
Video Face Swap
완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!
인기 기사
뜨거운 도구
메모장++7.3.1
사용하기 쉬운 무료 코드 편집기
SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.
스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경
드림위버 CS6
시각적 웹 개발 도구
SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)
뜨거운 주제
7711
15
1640
14
1394
52
1288
25
1232
29
Xiaohongshu 메모를 삭제하는 방법
Mar 21, 2024 pm 08:12 PM
Xiaohongshu 메모를 삭제하는 방법 Xiaohongshu 앱에서 메모를 편집할 수 있습니다. 다음으로 편집기는 Xiaohongshu 메모 삭제 방법에 대한 사용자 사진과 텍스트를 가져옵니다. 보세요! Xiaohongshu 사용 튜토리얼 Xiaohongshu 메모 삭제 방법 1. 먼저 Xiaohongshu 앱을 열고 메인 페이지로 들어가서 오른쪽 하단에 있는 [Me]를 선택하여 특별 영역으로 들어갑니다. 2. 그런 다음 내 영역에서 다음과 같이 메모 페이지를 클릭합니다. 3. 노트 페이지에 들어가서 오른쪽 상단에 있는 [점 3개]를 클릭합니다. 4. 마지막으로 기능 표시줄이 하단에 확장되고 [삭제]를 클릭하여 완료합니다.
Xiaohongshu에 게시한 메모가 누락된 경우 어떻게 해야 합니까? 방금 보낸 메모를 찾을 수 없는 이유는 무엇인가요?
Mar 21, 2024 pm 09:30 PM
Xiaohongshu 사용자로서 우리 모두는 게시된 노트가 갑자기 사라지는 상황을 경험해 본 적이 있을 것입니다. 이는 의심할 여지 없이 혼란스럽고 걱정스러운 일입니다. 이런 경우, 우리는 어떻게 해야 합니까? 이번 글에서는 "샤오홍슈에서 발행한 노트가 누락된 경우 어떻게 해야 할까요?"라는 주제를 중심으로 자세한 답변을 드리겠습니다. 1. Xiaohongshu에서 발행한 노트가 누락된 경우 어떻게 해야 합니까? 첫째, 당황하지 마십시오. 메모가 누락된 경우 침착함을 유지하는 것이 중요하며 당황하지 마십시오. 이는 플랫폼 시스템 장애 또는 운영 오류로 인해 발생할 수 있습니다. 출시 기록을 확인하는 것은 쉽습니다. Xiaohongshu 앱을 열고 "나" → "게시" → "모든 출판물"을 클릭하면 자신의 출판 기록을 볼 수 있습니다. 여기에서는 이전에 게시된 메모를 쉽게 찾을 수 있습니다. 3.다시 게시합니다. 발견된 경우
CLIP-BEVFormer: BEVFormer 구조를 명시적으로 감독하여 롱테일 감지 성능을 향상시킵니다.
Mar 26, 2024 pm 12:41 PM
위에 작성 및 저자의 개인적인 이해: 현재 전체 자율주행 시스템에서 인식 모듈은 중요한 역할을 합니다. 자율주행 시스템의 제어 모듈은 적시에 올바른 판단과 행동 결정을 내립니다. 현재 자율주행 기능을 갖춘 자동차에는 일반적으로 서라운드 뷰 카메라 센서, 라이더 센서, 밀리미터파 레이더 센서 등 다양한 데이터 정보 센서가 장착되어 다양한 방식으로 정보를 수집하여 정확한 인식 작업을 수행합니다. 순수 비전을 기반으로 한 BEV 인식 알고리즘은 하드웨어 비용이 저렴하고 배포가 용이하며, 출력 결과를 다양한 다운스트림 작업에 쉽게 적용할 수 있어 업계에서 선호됩니다.
C++에서 기계 학습 알고리즘 구현: 일반적인 과제 및 솔루션
Jun 03, 2024 pm 01:25 PM
C++의 기계 학습 알고리즘이 직면하는 일반적인 과제에는 메모리 관리, 멀티스레딩, 성능 최적화 및 유지 관리 가능성이 포함됩니다. 솔루션에는 스마트 포인터, 최신 스레딩 라이브러리, SIMD 지침 및 타사 라이브러리 사용은 물론 코딩 스타일 지침 준수 및 자동화 도구 사용이 포함됩니다. 실제 사례에서는 Eigen 라이브러리를 사용하여 선형 회귀 알고리즘을 구현하고 메모리를 효과적으로 관리하며 고성능 행렬 연산을 사용하는 방법을 보여줍니다.
C++sort 함수의 기본 원리와 알고리즘 선택을 살펴보세요.
Apr 02, 2024 pm 05:36 PM
C++정렬 함수의 맨 아래 계층은 병합 정렬을 사용하고 복잡도는 O(nlogn)이며 빠른 정렬, 힙 정렬 및 안정 정렬을 포함한 다양한 정렬 알고리즘 선택을 제공합니다.
인공지능이 범죄를 예측할 수 있을까? CrimeGPT의 기능 살펴보기
Mar 22, 2024 pm 10:10 PM
인공지능(AI)과 법 집행의 융합은 범죄 예방 및 탐지의 새로운 가능성을 열어줍니다. 인공지능의 예측 기능은 범죄 행위를 예측하기 위해 CrimeGPT(범죄 예측 기술)와 같은 시스템에서 널리 사용됩니다. 이 기사에서는 범죄 예측에서 인공 지능의 잠재력, 현재 응용 프로그램, 직면한 과제 및 기술의 가능한 윤리적 영향을 탐구합니다. 인공 지능 및 범죄 예측: 기본 CrimeGPT는 기계 학습 알고리즘을 사용하여 대규모 데이터 세트를 분석하고 범죄가 발생할 가능성이 있는 장소와 시기를 예측할 수 있는 패턴을 식별합니다. 이러한 데이터 세트에는 과거 범죄 통계, 인구 통계 정보, 경제 지표, 날씨 패턴 등이 포함됩니다. 인간 분석가가 놓칠 수 있는 추세를 식별함으로써 인공 지능은 법 집행 기관에 권한을 부여할 수 있습니다.
탐지 알고리즘 개선: 고해상도 광학 원격탐사 이미지에서 표적 탐지용
Jun 06, 2024 pm 12:33 PM
01 전망 요약 현재로서는 탐지 효율성과 탐지 결과 간의 적절한 균형을 이루기가 어렵습니다. 우리는 광학 원격 탐사 이미지에서 표적 감지 네트워크의 효과를 향상시키기 위해 다층 특징 피라미드, 다중 감지 헤드 전략 및 하이브리드 주의 모듈을 사용하여 고해상도 광학 원격 감지 이미지에서 표적 감지를 위한 향상된 YOLOv5 알고리즘을 개발했습니다. SIMD 데이터 세트에 따르면 새로운 알고리즘의 mAP는 YOLOv5보다 2.2%, YOLOX보다 8.48% 우수하여 탐지 결과와 속도 간의 균형이 더 잘 이루어졌습니다. 02 배경 및 동기 원격탐사 기술의 급속한 발전으로 항공기, 자동차, 건물 등 지구 표면의 많은 물체를 묘사하기 위해 고해상도 광학 원격탐사 영상이 활용되고 있다. 원격탐사 이미지 해석에서 물체 감지
워드에서 근수를 입력하는 방법을 함께 알아볼까요?
Mar 19, 2024 pm 08:52 PM
Word에서 텍스트 내용을 편집할 때 수식 기호를 입력해야 하는 경우가 있습니다. 어떤 사람들은 Word에서 근수를 입력하는 방법을 모르기 때문에 편집자에게 Word에서 근수를 입력하는 방법에 대한 튜토리얼을 친구들과 공유해달라고 요청했습니다. 그것이 내 친구들에게 도움이 되기를 바랍니다. 먼저 컴퓨터에서 Word 소프트웨어를 연 다음 편집하려는 파일을 열고 루트 기호를 삽입해야 하는 위치로 커서를 이동합니다. 아래 그림 예를 참조하세요. 2. [삽입]을 선택한 후, 기호에서 [수식]을 선택하세요. 아래 그림의 빨간색 원과 같이 3. 아래의 [새 수식 삽입]을 선택하세요. 아래 그림의 빨간색 원과 같이 4. [부수]를 선택한 후 해당 부수를 선택합니다. 아래 그림의 빨간색 원에 표시된 대로:
