Dotcpp  >  编程教程  >  算法基础  >  算法是什么?

算法是什么?

点击打开在线编译器,边学边练

算法的出现,远远早于计算机,所以关于算法的知识点也非常多,大家不要急于求成,而本篇将从算法的概念、特征、评价以及复杂度四个方面详细介绍算法,希望关于算法的内容给大家一个清晰的认识,方便大家在日后的运用有更深的概念。


一、算法的概念

算法(algorithm,[ˈælɡərɪðəm],计算程序):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。

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

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

程序 = 算法+数据结构


二、算法的特征

(1)可行性

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

(2)确定性

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

(3)有穷性

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

(4)输入

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

(5)输出

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


三、算法的评价

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

(1)正确性

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

(2)可读性

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

(3)健壮性

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


四、算法的复杂度

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

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

复杂度标记符号说明
常量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;


(2)空间复杂度:评估程序所需要的储存空间。空间复杂度一般不作考虑,一般都优先考虑时间复杂度。

以上是关于算法知识的介绍,有了基础概念的理解,方便后期我们学习算法的运用和实操。


本文固定URL:https://www.dotcpp.com/course/924

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)