本系列为C++算法学习系列,会介绍 算法概念与描述,入门算法,基础算法,数值处理算法,排序算法,搜索算法,图论算法, 动态规划等相关内容。本文为C+算法概念与描述部分。
【 1 】算法概念 【 2 】算法描述:自然语言描述、流程图描述、 伪代码描述
信息学奥赛算法是指用计算机解决问题的方法和技巧。其核心在于算法的设计和优化,包括时间复杂度和空间复杂度等方面的优化。下面是一些常见的算法概念介绍:
假设有两只没有刻度的桶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 时,排序结束。
**流程图描述:**通过图形化方式来表示算法的步骤和操作。例如,下图是一个简单的冒泡排序算法的流程图描述:
**伪代码描述:**通过一种类似编程语言的语法来描述算法的步骤和操作。伪代码通常比自然语言描述更具体和精确。例如,下面是一个用伪代码描述的冒泡排序算法:
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互相倒腾得到六升水。
算法的时间复杂度是衡量算法运行时间效率的一种指标,通常用大O表示法来表达。它描述了算法在处理问题时所需的时间资源,即算法的时间复杂度越低,算法的执行效率越高。
时间复杂度通常表示为一个函数T(n),其中n表示输入规模。时间复杂度可以分为以下几类:
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
int i = 1;
while(i<n)
{
i = i * 2;
}
线性对数阶O(nlogN) 其实非常容易理解,将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n * O(logN),也就是了O(nlogN)。
for(m=1; m<n; m++)
{
i = 1;
while(i<n)
{
i = i * 2;
}
}
for(x=1; i<=n; x++)
{
for(i=1; i<=n; i++)
{
j = i;
j++;
}
}
综上所述,算法的时间复杂度是评价算法效率的重要指标之一。在实际编程中,我们需要根据不同的需求选择不同的算法和数据结构,以提高程序的执行效率。算法的时间复杂度是衡量算法运行时间效率的一种指标,通常用大O表示法来表达。它描述了算法在处理问题时所需的时间资源,即算法的时间复杂度越低,算法的执行效率越高。