算法和算法分析

时间:2021-04-26 11:14:16

一:算法的基本概述

算法是为了解决某类问题而规定的一个有限长的操作序列。   一个算法必须满足以下个重要特性 1.有穷性 2.确定性   3.可行性4.有输入 5.有输出 二:设计算法的原则 1.正确性2.可读性3、健壮性4.高效率与低存储量需求三:算法的时间复杂度简介  语句频度:语句重复执行的次数  所有语句频度之和记做f(n),它是该算法所求解的问题规模n的函数; T(n)=O(f(n))当n->∞时,T(n)的数量级称为渐近时间复杂度,简称时间复杂度。              一个特定算法的“运行工作量”的大小,只依赖于问题的规模(通常用整数量n表示),或者说,它是问题规模的函数。与待处理数据的初态无关。  一个算法的时间复杂度还可以具体分为最好、最差(最坏)、平均三种情况讨论。最好情况下最容易求出,但没有多大实际意义最差情况下也容易求出,而且这是估计该算法执行时间的一个上界平均情况下最难计算:在很多情况下地输入数据集出现的概率难以确定。一般,算法的时间复杂度如无特别说明,则指最坏情况下的时间复杂度