龙潭书斋 -- 320




最优子结构动态规划算法最大的特性是:局部最优中产生整体最优。具体方法是:逐层迭代,从局部开始,一步一步走到整体。用动态规划求解最优化问题的第一步是描述最优解的结构,如果问题的一个最优解中包含了子问题的最优解,则该问题具有最优子结构当一个问题具有最优子结构时,我们才可以在分治法、动态规划、贪心策略等算法中进行选择在动态规划中,我们利用子问题的最优解来构造问题的一个最优解 寻找最优子结构时,可以遵循一种共同的模式:问题的一个解可以是做一个选择,如选择一个前一个装配站或者选择一个下标以在该位置分裂矩阵,选择完成后会得到一个或多个子问题假设对一个给定的问题,一直的是一个可以导致最优解的选择,我们不必去关系如何确定这个选择,只要假定它是已知的(与数学上的归纳证明方法是类似的)在已知这个选择后,要确定那些子问题会随之发生,以及如何最好的描述所得到的子问题空间利用一个“剪贴”(cut-and-paste)的技术,来证明在问题的一个最优解中,使用的子问题的解本身也必须是最优的,通过假设一个子问题的解都 不是最优解然后导出矛盾即可 动态规划以自底向上的方式来利用最优子结构,也就是说,首先找到子问题的最优解,解决子问题,然后找到问题的一个最优解,寻找问题的最优解需要在子问题中作出选择,即选择将用哪一个来求解问题 重叠子问题适用于动态规划方法求解的问题必须具有的第
#读书笔记    #技术帖    #算法    #算法导论   

200x200


二叉查找树 对于二叉树的任一节点,如果该节点的左子树都小于他,右子树都大于他,这棵树即被称为“二叉查找树”,又称“二叉排序树”因此,二叉查找树的中序遍历将产生一个由小到大的有序数列需要注意的

#读书笔记    #技术帖    #算法    #算法导论   

200x200


以期望线性时间做选择一般来说,中位数的查找算法都是基于先排序,后找中间位置的数字的算法,但是因为线性时间排序所收到的限制比较大,而如果使用基于比较的排序,时间复杂度将至少为O(nlogn),如何以线性

#读书笔记    #技术帖    #算法    #算法导论   

200x200


概述与堆排序一样,桶排序也是一个基于数据结构的排序算法,桶排序所基于的数据结构就是HashMap,由于在数据均匀分布的情况下,哈希表的遍历和插入的时间复杂度都是线性的,因此,桶排序在输入符合均匀分布时

#读书笔记    #技术帖    #算法    #算法导论   

200x200


概述基数排序是在计数排序基础上进行的一种线性时间排序,时间复杂度是O(n),空间复杂度是O(n*k)算法思路如下图所示:  是模拟老式穿卡机的排序算法 代码/* * f

#读书笔记    #技术帖    #算法    #算法导论   

200x200


算法说明基于比较的排序算法的本质都是基于决策树的,由于树的高度为O(logn),所以基于比较的排序算法在最坏情况下其时间复杂度不会低于O(nlogn)而计数排序并不是基于比较的,而是通过循环计数确定每

#读书笔记    #技术帖    #算法    #算法导论   

200x200


概述快速排序算是最常用的排序算法了,过程有些复杂,不过只要记住这个排序算法的思路是:每次循环结束的时候,基准元素左侧的所有元素值都小于他,右侧的所有元素值都大于他,之后对左右两个子序列分别进行递归,这

#读书笔记    #技术帖    #算法    #算法导论   
堆二叉堆数据结构是一种数组对象,是一棵特殊的完全二叉树,分为大根堆和小根堆对于小根堆,任何一个子树的根节点都小于其左右子树,大根堆则相反在堆排序算法中,我们使用大根堆,而小根堆通常用于构造优先级队列 堆排序/* * file: main.c * author: 龙泉居士 * date: 2012-12-28 21:55 */ #include <stdio.h> #include "function/function.h" int heap_sort (int *array, int n) { if (array == NULL || n<=0) { printf ("build_heap param error"); return -1; } else if (n == 1) return 0; build_heap (array, n); int i; for (i=n-1; i>0; --i) { exch (array, 0, i); con_heap (array, 0, i); } return 0;
#读书笔记    #技术帖    #算法    #算法导论   

200x200


概述程序设计算法中有一个很常用的策略,那就是分治策略 分治策略一般递归的执行三个步骤:分解问题解决问题合并结果 合并排序就是典型的分治策略下的排序算法,有两种实现方式,分别是自顶向

#读书笔记    #技术帖    #算法    #算法导论   
概述与插入排序极其类似的还有选择排序,每次选择未排序队列中的最小元素放到未排序队列的开头并将已排序队列元素数加一 代码#include <stdio.h> int choose_sort(int *array, int n) { if (array == NULL) { printf ("sort element error\n"); return -1; } int i, j; for (i=0; i<n; ++i) { int min = array[i], minpos = i; for (j=i+1; j<n; ++j) { if (array[j] < min) { min = array[j]; minpos = j; } } array[minpos] = array[i]; array[i] = min; } return 0; } int main () { int i, n=10; int array[10]; printf ("Please input 10 numbers:\n"); for (i=0; i!=n; ++i) scanf ("%d", &a
#读书笔记    #技术帖    #算法    #算法导论   



京ICP备15018585号