什么是算法?_拉杆给油不要慌的博客-程序员秘密

技术标签: 算法  c++  

一、算法的概念

        算法(algorithm)是解决一系列问题的清晰指令,也就是,能对一定规范的输入,在有限的时间内获得所要求的输出。

        简单来说,算法就是解决一个问题的具体方法和步骤。算法是程序的灵        魂。

程序 = 算法+数据结构

二、算法的特征

1.可行性

        算法中执行的任何计算步骤都可以分解为基本可执行的操作步,即每个计算步都可以在有限时间里完成(也称之为有效性)

2.确定性

        算法的每一步都要有确切的意义,不能有二义性。例如“增加x的值”,并没有说增加多少,计算机就无法执行明确的运算。

3.有穷性

        算法的有穷性是指算法必须在执行有限个步骤后终止。操作次数不宜过大,不能超过人们事先设定的时间限制。

4.输入

算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法已经给出了初始条件。

5.输出

一个算法可能有1个或多个输出,以反映输入数据加工后的代码,没有输出的算法是没有意义的!

三、算法的评价

通常一个好算法应该达到如下目标:

1.正确性

算法应该正确的解决问题。

2.可读性

算法应该具有较好的可读性,让人们理解算法的作用。

3.健壮性

输入非法数据时,算法也可以做出适当的反应,而不会产生奇奇怪怪的输出。

四、算法的复杂度

算法复杂度是指算法在变为可执行程序后所耗费的时间资源和内存。

时间复杂度:评估程序所需要的时间。

空间复杂度:评估程序所需要的储存空间。

        空间复杂度一般不作考虑,一般都优先考虑时间复杂度。

                                                常见时间复杂度     

复杂度 标记符号 说明
常量 O(1) 操作数量为常数,与输入数据的规模无关
对数 O(log2 n) 与输入数据的比例是 log2(n)
线性 O(n) 与输入数据成正比
平方 O(n²) 与输入数据规模的比例为平方
立方 O(n³) 与输入数据规模的比例为立方
指数

O(2ⁿ)

O(kⁿ)

O(n!)

快速增长,尽量减少这种代码

各种代码示范:

1.O(1)级代码 

//计算长方形面积
int a,b;
cin>>a>>b;
int s = a*b;
cout<<s;

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.O(n)级代码

//计算n的阶乘
int n;
cin>>n;
int ji = 1;
for(int i = 1 ; i<=n ; i++){
    ji*=i;
}
cout<<ji<<endl;

4.O(n²)级代码

​
​//相邻比较法排序
int a[10000],n;
cin>>n;
for(int i = 1 ; i<=n ; i++) cin>>a[i];
for(int i = 1 ; i<=n ; i++){
    for(int j = i+1 ; j<=n+1 ; j++){
        if(a[i]>a[j])
            swap(a[i],a[j])
    }
}

​

​

5.O(n*log2 n)级代码

//STL快速排序
sort(a+1,a+n+1);

6.可以估算时间的代码

#include<iostream>
#include<ctime>
using namespace std;
int cnt;
int main()
{
	int begintime = clock();
	for(int i = 0 ;i<5e8 ; i++) cnt++;
	int endtime = clock();
	cout<<"开始时间"<<begintime<<endl;
	cout<<"结束时间"<<endtime<<endl;
	cout<<"运行时间"<<endtime-begintime<<endl;

	return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Jerry_qbw/article/details/125142438

智能推荐

【聊天表情包小程序的开发】之小程序源码分享_哆糖表情小程序源码_冰的学习时光的博客-程序员秘密

目前已经完成了表情的展现、分享、搜索等功能,这几天住了个院,可能需要过几天才能更新了,现在先把源码放出来,供大家学习和研究。后续会更新更多功能,包括且不限于 用户收藏、表情制作、表情上传、广告等功能,希望大家关注小程序和git,会不定时更新哦!!!主要页面样式如下:在线测试小程序二维码git上开源的工程地址为:https://gitee.com/gllfeixiang/bqminiapp...

android最全学习资料及路线整理分享 (安卓视频教程 从入门到大师 android开发环境搭建 windows和MAC 安卓源码大全4000套)_小黄人软件的博客-程序员秘密

android最全学习资料整理分享 (安卓视频教程 从入门到大师 android开发环境搭建 windows和MAC 安卓源码大全4000套)

java多线程的同步和死锁_兰亭牡丹的博客-程序员秘密

多线程同步对于完成应用程序的完成性提供了技术支持,是很重要的部分

【CV】Transformer相关的CV文章_风度78的博客-程序员秘密

https://github.com/dk-liang/Awesome-Visual-Transformerhttps://github.com/IDEACVR/awesome-detection-transformer本文主要包含跟Transformer相关的CV文章,用简短的话来描述一下涉及到文章的核心idea。可以看作是vision transformer的idea...

迷宫问题求解--完整可编译源码_迷宫求解代码_很奇怪的打野的博客-程序员秘密

经典迷宫问题求解,编译已经通过并且大作业验收,笔者总共写过两次迷宫,第一次是在C语言期末小作业使用递归写的,第二次在暑假小学期使用BFS算法写的,给初入C语言的小伙伴借鉴一下吧(笔者当时写一个小破迷宫花了一周,因为实在找不到参考,网上的代码很杂很乱,绝大部分不能编译,对新手很不友好,各种定义新手很难看不懂,所以我当时就有想法想着给C语言初学者一个好的学习代码!可以少走弯路!)创建迷宫无非就是两步,第一构建迷宫,第二走迷宫,创建迷宫呢,得先想好怎么存储迷宫,最简单的办法就是数组,然后怎么构建迷宫呢?笔者时间

Oracle数据库泵的备份与恢复_小黄人软件的博客-程序员秘密

Oracle数据库泵的备份与恢复目录一、数据库备份和恢复前的准备...11、给数据库用户授权并创建DIRECTORY对象...1_Toc388455817二、数据泵的备份和恢复...11、     数据库备份...12、     数据库恢复...2三、进入交互模式...4 一、数据库备份和恢复前的准备1、给数据库用户授权并创建

随便推点

跑通GVINS——港科大新作_小海盗haner的博客-程序员秘密

港科大新作GVINS简介0.简介1.环境2.跑通GVINS3.数据集0.简介港科大又一力作!vins-mono以及vins-fusion升级版GVINS重磅发布!终于有一个包含GNSS紧耦合的方法了,加紧学习!GVINS是一个基于非线性优化的系统,它将 GNSS 原始测量与视觉和惯性信息紧密融合,以实现实时和无漂移的状态估计。通过结合 GNSS 伪距和多普勒频移测量,GVINS 能够在复杂环境中提供平滑一致的 6-DoF 全局定位。系统框架和VIO部分改编自VINS-Mono。我们的系统包含以下功能

小黄人软件的故事 -----程序源码,定制专家_小黄人软件的博客-程序员秘密

小黄人软件来历如果不知道在网上卖什么,可以一个一个地去尝试!!!我最初也不知道卖什么,我就上网,一个一个地看,服装无人问津,不行,太多人花钱做推广。换成扭扭车,儿童玩具,三个月卖出几百辆,营业额几万,我还一边上班(上班8小时+中午休息1小时+来回路上2小时)一边卖,回来还得洗衣服买菜做饭,货物打包发叫快递发货,周六日还有空出去逛街。关键是眼睛还痛的厉害,简直不能看屏。后来扭扭车

拜托,别再问怎么深入学习分布式架构了!_weixin_33690963的博客-程序员秘密

2019独角兽企业重金招聘Python工程师标准&gt;&gt;&gt; ...

【C++求解组原习题】Float型数据,IEEE754 单精度浮点数表示,32位_kin55的博客-程序员秘密

大家好,今天我又写了一道计算机组原习题,是这样子的。题目和题解都来自与https://www.nowcoder.com/questionTerminal/3676093580344964af739b9e33a5463bfloat 型数据通常用 IEEE754 单精度浮点数格式表示。若编译器将 float 型变量 x 分配在一个 32 位浮点寄存器 FR1 中,且 x=-8.25,则 FR...

好程序员web前端系列之CSS3-3D_weixin_30311605的博客-程序员秘密

好程序员web前端系列之CSS3-3D,什么是3d的场景呢? 2d场景,在屏幕上水平和垂直的交叉线x轴和y轴3d场景,在垂直于屏幕的方法,相对于3d多出个z轴Z轴:靠近屏幕的方向是正向,远离屏幕的方向是反向CSS3中的3D变换主要包括以下几种功能函数:3D位移:CSS3中的3D位移主要包括translateZ()和translate3d()两个功能函数; 3D旋转:CSS3中的3D旋转...

QImage与QPixmap区别_图像qimage格式和qpixmap格式是什么意思_not so perfect的博客-程序员秘密

原因:关于这个话题,我其实本人刚开始在windows下进行Qt开发时,并没有太在意?当突然被问到具体区别时,我突然就懵了。特意整理??参考网址:https://www.cnblogs.com/s_agapo/archive/2012/03/14/2395603.htmlhttps://blog.csdn.net/ailinty/article/details/8964431https:/...

推荐文章

热门文章

相关标签