商务网站建设实训结论,微信短网址在线生成,深圳小程序开发方案,做网站金山区算法的概念
算法#xff08;algorithm#xff09;是解决一系列问题的清晰指令#xff0c;也就是#xff0c;能对一定规范的输入#xff0c;在有限的时间内获得所要求的输出。 简单来说#xff0c;算法就是解决一个问题的具体方法和步骤。算法是程序的灵魂 一、算法的特征…算法的概念
算法algorithm是解决一系列问题的清晰指令也就是能对一定规范的输入在有限的时间内获得所要求的输出。 简单来说算法就是解决一个问题的具体方法和步骤。算法是程序的灵魂 一、算法的特征
1. 可行性 算法中执行的任何计算步骤都可以分解为基本可执行的操作步骤即每个计算步都可以在有限时间里完成也称之为有效性
2. 确定性 算法的每一步都要有确切的意义不能有二义性。例如“增加x的值”并没有说增加多少计算机就无法执行明确的运算。
3. 有穷性 算法的有穷性是指算法必须在执行有限个步骤后终止。操作次数不宜过大不能超过人们事先设定的时间限制。
4. 输入 算法有0个或多个输入以刻画运算对象的初始情况所谓0个输入是指算法已经给出了初始条件。
5. 输出 一个算法可能有1个或多个输出以反映输入数据加工后的代码没有输出的算法是没有意义的 二、算法的评价
一个好算法应该达到一下目标
1. 正确性 算法应该正确的解决问题。 2. 可读性 算法应该具有较好的可读性让人们理解算法的作用。 3. 健壮性 输入非法数据时算法也可以做出适当的反应而不会产生奇奇怪怪的输出。 三、算法复杂度
算法复杂度 指算法在变为可执行程序后所消耗的时间资源和内存 时间复杂度 评估程序所需要的时间 空间复杂度 评估程序所需要的储存空间一般不做考虑一般都优先考虑时间复杂度
常见时间复杂度
复杂度标记符号说明常量O(1)操作数量为常数与输入数据的规模无关对数O(log2 n)与输入数据的比例是 log2n线性O(n)与输入数据成正比平方O(n²)与输入数据规模的比例为平方立方O(n³)与输入数据规模的比例为立方指数O(2ⁿ)O(kⁿ)O(n!)快速增长尽量减少这种代码 代码
1.O(1)级代码
//计算长方形面积
int a,b;
cinab;
int s a*b;
couts;2.O(log2 n)级代码
//二分查找
int search(int nums[], int size, int target) //nums是数组size是数组的大小target是需要查找的值
{int left 0;int right size - 1; // 定义了target在左闭右闭的区间内[left, right]while (left right) { //当left right时区间[left, right]仍然有效int middle left ((right - left) / 2);//等同于 (left right) / 2防止溢出if (nums[middle] target) {right middle - 1; //target在左区间所以[left, middle - 1]} else if (nums[middle] target) {left middle 1; //target在右区间所以[middle 1, right]} else { //既不在左边也不在右边那就是找到答案了return middle;}}//没有找到目标值return -1;
}
3.On级代码
//计算n的阶乘
int n;
cinn;
int ji 1;
for(int i 1 ; in ; i){ji*i;
}
coutjiendl;4.O(n²级代码
//相邻比较法排序
int a[10000],n;
cinn;
for(int i 1 ; in ; i) cina[i];
for(int i 1 ; in ; i){for(int j i1 ; jn1 ; j){if(a[i]a[j])swap(a[i],a[j])}
}5.O(n*log2 n)级代码
//STL快速排序
sort(a1,an1);6.可以估算时间的代码
#includeiostream
#includectime
using namespace std;
int cnt;
int main()
{int begintime clock();for(int i 0 ;i5e8 ; i) cnt;int endtime clock();cout开始时间begintimeendl;cout结束时间endtimeendl;cout运行时间endtime-begintimeendl;return 0;
}
