算法导论（二）-------分治（D&C）思想之最大子数组问题

分治思想在算法设计中分治思想在是一个十分重要的算法设计思想，我们可以在实际中多思考这种算法。这种算法主要时用函数的递归来进行实现的。主要的过程如下：分： 将问题分为两个或者多个子问题治 解决每一个子问题合 最后自要将我们分开的子问题进行合并为我们需要解决的问题比较官方的话就先写道这里了下面用实例来体...

《算法导论》学习笔记之Chapter9中位数和顺序统计量

第9章 中位数和顺序统计量先定义：在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。一个中位数是它所属集合的“中点元素”。当n是奇数时，中位数是唯一的，位于i=n/2处。当n为偶数时，中位数有两个，分别位于i = n/2和i=n/2+1处。不考虑n的奇偶性，中位数总是出现在i=(...

算法导论学习笔记——7快速排序

7快速排序void QuickSort(ll A[],ll p,ll r){if(p<r){ll q=Partition(A,p,r);QuickSort(A,p,q-1);QuickSort(A,q+1,r);}}ll Partition(ll A[],ll p,ll r){x=A[r];i...

算法导论之使用动态规划法求解矩阵连乘最小乘法次数

最近看到使用动态规划法求解矩阵连乘最小乘法次数，网上的一些copy主，只是copy，也不改错。本文已将一些不正确的错误更改。问题描述:给定n个矩阵:A1,A2,…,An,其中Ai与Ai+1是可乘的,i=1,2…,n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入...

算法导论 之 动态规划 - 装配线调度问题[C语言]

1 问题描述 现有两条装配线，Sij表示第i条上完成第j道工序的装配站。汽车完成组装需要依次完成1~n工序。请找出完成装配并离开装配线的最快路线。符号说明：①、ei：汽车进入装配线i的时间，i=1,2②、xi：汽车离开装配线i的时间③、aij：在装配站Sij完成装配需要的时间④、tij：在装配站Si...

c++实现算法导论，归并排序

假设桌上有两堆牌面朝上的牌，每堆都已排序，最小的牌在顶上。我们希望把这两堆牌合并成单一的排好序的输出堆，牌面朝下地放在桌上。我们的基本步骤包括在牌面朝上的两堆牌的顶上两张牌中选取较

MIT算法导论公开课之第5课 线性时间排序

排序算法的速度取决于所使用的计算机模型里允许的操作。常见排序快速排序（Θ(nlgn)）（不稳定排序）（交换过程会破坏稳定性）堆排序 （Θ(nlgn)）（不稳定排序）归并排序（Θ(nlgn)）（稳定性排序）插入排序（Θ(n^2)） （稳定性排序）比较排序模型允许比较数的大小的操作。最快的时间复杂度为...

<算法导论>学习笔记(2)

Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices. 是否具有扎实的算...

算法导论学习笔记(2)

Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices. 是否具有扎实的算...

洛谷【P1523】旅行商的背包（算法导论 15-1） 题解

P1523 旅行商简化版题目背景欧几里德旅行商\((Euclidean Traveling Salesman)\)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解，但是有办法在多项式时间内求出一个较优解。为了简化问题，而且保...

插入排序-算法导论笔记

插入排序对于少量的数据它是一个有效的算法。插入排序的工作方式像人手里的扑克牌一样。开始时我们手里为空并且桌子上的牌面向下。然后我们每次从桌上拿走一张牌并将它插入手里正确的位置。为了把这种牌插入正确的位置，我们要从右到左将它和已在手中的牌进行比较。如下图： 伪代码:INSERTION-SORT(A) ...

《算法导论》第三版 2.3.1 归并排序

MERGE-SORT(A,p,r)if p<r q = (p+r)/2 MERGE-SORT(A,p,q) MERGE-SORT(A,q+1,r) MERGE(A,p,q,r)归并排序利用递归将一个大数组不断的从中间对半分成两个小的数组直到数组中只剩下一个元素，然后通过...

重温算法导论（五） 归并排序

归并排序，就是利用递归的思维，解决排序的问题首先嘉定L R中已经是排好序的数据，利用Merge函数，将他们合并起来Merge函数伪代码Merge(A, p, q, r)n1 = q - p + 1n2 = r - qL[n1] = A[p, q]R[n2] = A[q+1, r]j = 0i = 0...

重温算法导论（二） 快速排序

快速排序的思想，就是分而治之的思想，也就是把问题分成两个，再继续分解，到最后。具体举例的思想如下：算法导论原书的例子：其实现的伪代码：将一个问题，分解为两个子串的排序问题，利用递归，继续对子串排序，最后实现整串排序QUICKSORT(A,p,r) //原地重排 p,r 对应下标if p < r...

算法导论快速排序之python和ｃ++实现

１．快速排序快速排序是一种比较快的排序算法，其主要思想是：具体思想不再赘述。下面给出具体代码实现。２．python3实现#quick sort#python3#Yanglin Tudef partition(arr, p, r): x = arr[r] i = p-1 for j ...

【算法导论】 内部排序算法总结

排序名称时间复杂度空间复杂度稳定性直接插入排序O(n^2)O(1)稳定折半插入排序O(n^2)O(1)稳定希尔排序O(n^2)O(1)不稳定冒泡排序O(n^2)O(1)稳定快速排序O(n*logn)O(1)不稳定简单选择排序O(n^2)O(1)不稳定堆排序O(n*logn)O(1)不稳定归并排序O(...

【算法导论】--分治策略Strassen算法（运用下标运算）【c++】

由于偷懒不想用泛型，所以直接用了整型来写了一份 ①首先你得有一个矩阵的class Matrix ②Matrix为了方便用下标进行运算， Matrix的结构如图：(我知道我的字丑。。。) Matrix.h代码如下：(个人并不喜欢把代码全写在一块，对于阅读者是相当巨大的负担，其实自己受不了（逃）) Ma ...

《算法导论》第六章优先队列 python 实现

优先队列是堆排序的一个应用 ：支持的操作：返回最大值，去掉并返回最大值，插入元素def max_heapify(A, i, heap_size): l = 2 * i r = 2 * i + 1 if l <= heap_size and A[l-1] > A[i-1]...