算法01-算法概念与描述

简介: 算法01-算法概念与描述


总结


本系列为C++算法学习系列,会介绍 算法概念与描述,入门算法,基础算法,数值处理算法,排序算法,搜索算法,图论算法, 动态规划等相关内容。本文为C+算法概念与描述部分。


大纲要求

【 1 】算法概念

【 2 】算法描述:自然语言描述、流程图描述、 伪代码描述


算法概念

信息学奥赛算法是指用计算机解决问题的方法和技巧。其核心在于算法的设计和优化,包括时间复杂度和空间复杂度等方面的优化。下面是一些常见的算法概念介绍:


  1. 排序算法:将一组数据按照指定的规则进行排序的算法,包括冒泡排序、快速排序、归并排序等。
  2. 搜索算法:通过遍历某个数据集合来查找特定元素的算法,包括二分查找、深度优先搜索、广度优先搜索等。
  3. 图论算法:用于解决图论相关问题的算法,包括最短路径算法、最小生成树算法、拓扑排序等。
  4. 动态规划算法:将一个问题分解成一个个子问题来求解的算法,包括最大子序列和、最长公共子序列等。
  5. 贪心算法:在每一步选择中都采取在当前状态下最优的选择,从而希望导致结果是全局最优的算法,包括背包问题等。
  6. 分治算法:将问题分解成多个小问题来求解的算法,包括快速排序、归并排序等。
  7. 字符串算法:用于解决字符串相关问题的算法,包括KMP算法、Trie树等。


举个例子:量水问题

假设有两只没有刻度的桶A和B,A可以装7升水,B可以装5升水,问:如何通过A和B互相倒腾得到六升水。


解:


将A装满(0升变7升)

将A的水倒向B,(A从7升剩2升,B变5升)

将B倒掉,

将A(2升b变0)倒向B(0变2升)

将A装满水

将A倒向B(此时A从7升变4升,B从2升变5升)

将B倒掉,

将A(4升)倒向B(从0升变4升)

将A装满水

将A再倒向B(从4升变5升,A此时剩余6升。


简化步骤:


将下面(2,3,4,5)重复两次

2、将A装满

3、将A的水倒向B

4、将B倒掉

5、将A倒向B

6、将A装满水

7、将A再倒向B


算法简单来说就是准确描述的“操作步骤”。

什么是计算机算法 —— 从特殊到一般的追求。

上面的例子我们给定的是具体的值,但是计算机算法是要追求一般的规律。

我们可以理解为数学公式,它不是具体的值,但解释了一般规律。


算法描述

算法描述:自然语言描述、流程图描述、 伪代码描述

**自然语言描述:**通过自然语言来描述算法的步骤和操作。例如,冒泡排序算法可以用如下自然语言描述:从数组的第一个元素开始,依次比较相邻的两个元素,如果前一个元素大于后一个元素,则交换它们的位置,直到将最大的元素移动到数组的最后一个位置。重复上述操作,直到所有元素都排好序为止。


初始化变量 i 和 j 为 0,表示当前需要比较的元素下标。

在数组 A 中比较 A[i] 和 A[j] 两个元素,如果 A[i] 大于 A[j],则交换它们的位置。

将 j 增加 1,如果 j < n,则回到步骤 2;否则,将 i 增加 1,将 j 重置为 i,如果 i < n-1,则回到步骤 2。

当 i >= n-1 时,排序结束。


**流程图描述:**通过图形化方式来表示算法的步骤和操作。例如,下图是一个简单的冒泡排序算法的流程图描述:

a97bfed7e0bd104933bccf9e562ea768_d4d65da6780d432b9af6a7ae9cf8cdac.png


**伪代码描述:**通过一种类似编程语言的语法来描述算法的步骤和操作。伪代码通常比自然语言描述更具体和精确。例如,下面是一个用伪代码描述的冒泡排序算法:


procedure bubbleSort(A : list of sortable items)
    n = length(A)
    repeat
        swapped = false
        for i = 1 to n-1 do
            if A[i] > A[i+1] then
                swap(A[i], A[i+1])
                swapped = true
            end if
        end for
        n = n - 1
    until not swapped
end procedure

假设有两只没有刻度的桶A和B,A可以装7升水,B可以装5升水,问:如何通过A和B互相倒腾得到六升水。

8a3279a0092226c1b468bf2b19c580f5_26633b6657de4d82b3c0b41fe8189548.png


算法的时间复杂度

算法的时间复杂度是衡量算法运行时间效率的一种指标,通常用大O表示法来表达。它描述了算法在处理问题时所需的时间资源,即算法的时间复杂度越低,算法的执行效率越高。


时间复杂度通常表示为一个函数T(n),其中n表示输入规模。时间复杂度可以分为以下几类:


1.常数时间复杂度O(1),表示算法的执行时间与输入规模 n 无关,比如说访问数组中的一个元素。

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

2.线性时间复杂度O(n),表示算法的执行时间与输入规模 n 成正比,比如说遍历一个数组。

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

3.对数时间复杂度O(logn),表示算法的执行时间与输入规模 n 的对数成正比,通常出现在二分查找等算法中。

int i = 1;
while(i<n)
{
    i = i * 2;
}

3.线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解,将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n * O(logN),也就是了O(nlogN)。


for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

4.平方时间复杂度O(n^2),表示算法的执行时间与输入规模 n 的平方成正比,通常出现在多重循环嵌套的算法中。

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

指数时间复杂度O(2^n),表示算法的执行时间与输入规模 n 的指数成正比,通常只出现在具有递归性质的算法中。

2e4bbb8698714aeac97f9aed8c5afa16_b2ee18280d6947b9b1cee48c7916574f.png


综上所述,算法的时间复杂度是评价算法效率的重要指标之一。在实际编程中,我们需要根据不同的需求选择不同的算法和数据结构,以提高程序的执行效率。算法的时间复杂度是衡量算法运行时间效率的一种指标,通常用大O表示法来表达。它描述了算法在处理问题时所需的时间资源,即算法的时间复杂度越低,算法的执行效率越高。


4111e3c56c3ca4163896ea4004a787a1_d530f251860b4fbc853a19c479e89df8.png

14466502de6f66d419fd85b8e5b44267_8706e23d731143618e752cdb30904bee.png


d51985f381a63591bc7cfba3270ca465_2c03438aaed540dda3f94bd5c37dedba.png

相关文章
|
3月前
|
人工智能 自然语言处理 算法
算法01-算法概念与描述
算法01-算法概念与描述
|
4月前
|
消息中间件 算法 JavaScript
JavaScript算法和数据结构:描述一下栈和队列的特点及应用场景。
JavaScript算法和数据结构:描述一下栈和队列的特点及应用场景。
40 0
|
3月前
|
监控 算法 Java
垃圾回收机制与性能调优:描述Java虚拟机(JVM)的垃圾回收算法,并解释为什么需要这些算法。如何使用Java内存分析工具(如VisualVM、JConsole或MAT)来识别和解决内存泄漏问题?
垃圾回收机制与性能调优:描述Java虚拟机(JVM)的垃圾回收算法,并解释为什么需要这些算法。如何使用Java内存分析工具(如VisualVM、JConsole或MAT)来识别和解决内存泄漏问题?
30 1
|
4月前
|
算法 Java
算法和算法的描述不匹配
算法和算法的描述不匹配
28 1
|
11月前
|
机器学习/深度学习 存储 算法
图像特征提取与描述_角点特征03:Fast算法+ORB算法
我们前面已经介绍过几个特征检测器,它们的效果都很好,特别是SIFT和SURF算法,但是从实时处理的角度来看,效率还是太低了。为了解决这个问题,Edward Rosten和Tom Drummond在2006年提出了FAST算法,并在2010年对其进行了修正。
332 0
|
11月前
|
资源调度 算法 机器人
图像特征提取与描述_角点特征02:SIFT算法+SURF算法
前面两节我们介绍了Harris和Shi-Tomasi角点检测算法,这两种算法具有旋转不变性,但不具有尺度不变性,以下图为例,在左侧小图中可以检测到角点,但是图像被放大后,在使用同样的窗口,就检测不到角点了。
118 0
|
11月前
|
算法 API 计算机视觉
图像特征提取与描述_角点特征01:Harris算法+Shi-Tomas算法
Harris角点检测的思想是通过图像的局部的小窗口观察图像,角点的特征是窗口沿任意方向移动都会导致图像灰度的明显变化
110 0
|
12月前
|
存储 算法 C++
|
机器学习/深度学习 算法 数据挖掘
|
自然语言处理 算法 Java
【Java数据结构及算法实战】系列002:算法的四种描述方式
本节是《Java数据结构及算法实战》系列的第2节,主要介绍描述算法的常用的4种方式。 要定义一个算法,我们可以用自然语言、流程图、伪代码的方式描述解决某个问题的过程或是编写一段程序来实现这个过程。比如,在前面所举的“学生信息管理系统”例子中,我们希望实现添加用户、删除用户、查询用户三个算法。
306 0
【Java数据结构及算法实战】系列002:算法的四种描述方式