数据结构（二）——算法的基本概念

我就是我 2021-10-30 02:14 297阅读 0赞

# 一、概念： #

*  算法是特定问题求解步骤的描述
 *  在计算机中表现为指令的有限序列
 *  是独立存在的一种解决问题的方法和思想
 *  对于算法而言，语言不重要，重要的是思想

# 二、算法和数据结构的区别： #

*  数据结构只是静态描述了数据元素之间的关系
 *  高效的程序需要在数据结构的基础上设计和选择算法，即程序=数据结构+算法
 *  算法是为解决实际问题而设计的
 *  数据结构是算法需要处理的问题载体
 *  数据结构与算法相辅相成

# 三、算法效率的度量——复杂度度量： #

## 3.1 算法复杂度度量的方式： ##

*  事前分析估算
 *  依据统计方法对算法效率进行估算

## 3.2 影响算法效率的主要因素 ##

1.  算法采用的策略和方法
2.  问题的输入规模
3.  编译器所产生的代码
4.  计算机执行速度

## 3.3 常用的度量方法： ##

时间复杂度和空间复杂度

### 3.3.1 时间复杂度： ###

>       通过计算算法里总的操作数量衡量算法效率
> 
> 因为算法最终是由具体的计算机指令实现，每个指令在计算机CPU上运行的时间是固定的，这样通过具体的n步就可以推导出算法的复杂度

以下表为例，当程序执行相同的次数时不同的算法执行的次数是不同的

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NzY0MTI5_size_16_color_FFFFFF_t_70][]

在评估算法的好坏时要注意：

> 1.  判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
> 2.  在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏的时间复杂度

## 大O表示法; ##

1.  算法效率严重依赖操作（operation）数量
2.  在判断时首先要关注操作数量的最高次项
3.  操作数量的估算可以作为时间复杂度的估算

比如下面是关于算法效率的计算：

*  O(5) = O(1)
 *  O（2n+1）= O(2n) = O(n)
 *  O(n^2 + n +1) = O(n^2)
 *  O(3n^3 +2n +1) = O(3n^3) = O(n^3)

常见的时间复杂度模型：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NzY0MTI5_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NzY0MTI5_size_16_color_FFFFFF_t_70 2][]

### 3.3.2 空间复杂度度量 ###

> 通过计算算法的存储空间来实现，即看程序对内存的需求

比如：

S（n） = O(f(n))

其中n为问题规模，f（n）为在问题规模为n时所占用的存储空间的函数

大O表示法同样适用于算法的空间复杂度

注：当算法执行时所需要的空间是常数时，空间复杂度为O(1)

![20190819172814816.png][]

## 3.4 空间与时间策略 ##

*  多数情况下，算法执行时所用的时间更令人关注
 *  如果有必要，可以通过**增加**空间复杂度来**降低**时间复杂度
 *  同理，也可以通过**增加**时间复杂度来**降低**空间复杂度

例子：一个数组中存放了从1-1000的随机整数，求数组中出现次数最多的那个数。

//统计字符串中出现次数最多的那个数
    int main()
    {
    	int a[] = {1,2,4,1,6,1,8,9};
    	int x[1000] = {0};
    	int max=0;
    	//cout << sizeof(a)/sizeof(*a) << endl;
    	int len = sizeof(a) / sizeof(*a);
    	
    	for (int i = 0; i < len; i++) //遍历数组求每个数字出现的次数，然后记录下来
    	{
    		int b = a[i] - 1;
    		x[b]++;
    	}
    	for (int i = 0; i < 1000; i++)//扫描数组求最大数
    	{
    		if (max < x[i])
    		{
    			max = x[i];
    		}
    	}
    	for (int i = 0; i < len; i++) //输出
    		if (x[i] == max)
    		{
    			cout << i + 1 << " " ;
    			cout << "出现次数：" << x[i] << endl;
    		}
    		
    	return 0;
    }

![20190819210723140.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NzY0MTI5_size_16_color_FFFFFF_t_70]: /images/20211029/a0f09d4b011743b0b96d85135a535dc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NzY0MTI5_size_16_color_FFFFFF_t_70 1]: /images/20211029/d9cd2b9e7cdc4c70a72804fcd7f73fea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NzY0MTI5_size_16_color_FFFFFF_t_70 2]: /images/20211029/a5aac59680e2459e934a91565521713b.png
[20190819172814816.png]: /images/20211029/84f9866de7944bfdb6c8e60ce5b9344d.png
[20190819210723140.png]: /images/20211029/73bdd9e385624097b1aa9c1d196d61d4.png