初阶算法（1）：通过简单的排序算法来认识时间复杂度

系统管理员 2023-10-13 21:54 2阅读 0赞

## 系列文章目录 ##

第一章 初阶算法（1）：通过简单的排序算法来认识时间复杂度

第二章 [初阶算法（2）：进行详细地介绍插入排序的细节和时间复杂度][2]

第三章 [初阶算法（3）：二分法的讲解与实现（C语言），以及二分不止光在有序数组中的应用][3_C]

--------------------

**目录**

系列文章目录

前言

一、时间复杂度是什么？

常数时间的操作：

时间复杂度：

排序：

二、额外空间复杂度是什么？

总结

--------------------

## 前言 ##

> 总所周知，**算法**是**程序员必须要学习的一项内容**，而*小编是个菜鸟，所以将笨鸟先飞*，在这一系列，我会将我学习算法的亲身经历描写下来，将所学内容都记录下来，希望看到这篇文章的小伙伴**一起加油！**
> 
> 在网上进行搜索算法学习，有一个大佬（英雄哪里来）也是先从排序入手，我也会进行适当的借鉴大佬的笔记。

--------------------

## **一、时间复杂度是什么？** ##

在认识时间复杂度之前，我们先引出一个知识：**常数时间的操作**。

### 1.1 常数时间的操作： ###

>  我们在写代码的时候会写一些指令，这些**指令与数据量无关**，是一个**固定时间**的操作，这就是常数时间的操作。

下面是一些例子：

> 一些表达式操作，数组寻址，从数组中取一个数等等。

在认识完常数时间的操作后，我们来**通过排序进行认识时间复杂度**。

### 1.2 时间复杂度： ###

#### 1.2.1 排序： ####

首先，先来讲解选择排序算法。选择排序应该是最简单的排序了，下面是一个动图，（是借鉴英雄哪里来大佬的）。（[英雄从哪里来][Link 1]）

![1b1ec4fcf6024ad4a659fab5f21a7075.gif_pic_center][]

在计算时间复杂度时，一般是考虑**最坏步骤（所有步骤都进行）**。在选择排序中，

![16074b2fee1c45bdb3f35479b48fe88d.png][]

int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int arr[10000];
    	int minIndex = 0;
    	int temp = 0;
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d", &arr[i]);
    	}
    	for (int i = 0; i < n; i++)
    	{
            minIndex = i;
    		for (int j = i + 1; j < n; j++)
    		{
    			if (arr[minIndex] > arr[j])
    			{
    				minIndex = j;
    			}
    		}
    		temp = arr[i];
    		arr[i] = arr[minIndex];
    		arr[minIndex] = temp;
    	}
    	for (int i = 0; i < n; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	return 0;
    }

> 判断一个算法的时间好坏，**（1）****先看两者的时间复杂度的指标**：如果说两个算法流程的时间复杂度相同，则**（2）****用一个数据量很大的样本去跑**，看那个时间少。常数操作固定的时间也有差距。

## 二、额外空间复杂度是什么？ ##

额外空间复杂度是**流程在执行过程中额外申请的空间大小**。

--------------------

## 总结 ##

以上就是今天要讲的内容，本文仅仅简单介绍了时间复杂度和额外空间复杂度。希望大家看完以后，进行点评，谢谢大家！

[2]: http://t.csdn.cn/np95m
[3_C]: http://t.csdn.cn/n16nE
[Link 1]: http://t.csdn.cn/pk522
[1b1ec4fcf6024ad4a659fab5f21a7075.gif_pic_center]: https://img-blog.csdnimg.cn/1b1ec4fcf6024ad4a659fab5f21a7075.gif#pic_center
[16074b2fee1c45bdb3f35479b48fe88d.png]: https://img-blog.csdnimg.cn/16074b2fee1c45bdb3f35479b48fe88d.png