数据结构（1）算法复杂度_数据结构算法输入的列子和特征

1.什么是数据结构？

        数据结构（Data Structure）是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

        数据结构是计算机科学中的一个重要概念，它用于组织和存储数据，以便能够高效地访问和操作数据。数据结构可以被看作是一种特定的数据组织方式，它定义了数据之间的关系和操作。

        常见的数据结构包括数组、链表、栈、队列、树、图等。每种数据结构都有其特定的优势和适用场景。例如，数组可以在常数时间内访问任意位置的元素，但在插入和删除元素时需要移动其他元素，而链表则可以在常数时间内插入和删除元素，但访问元素的时间复杂度较高。

        数据结构的选择取决于问题的需求和特点。对于大规模数据的快速检索，通常使用树或哈希表等高效的数据结构。而对于需要保持元素顺序的场景，可以选择使用数组或链表。

        掌握数据结构对于编写高效的算法和程序至关重要。了解不同数据结构的特点和操作，可以帮助我们选择合适的数据结构，并设计出更高效的算法来解决问题。

2.什么是算法

        算法（Algorithm）：就是定义良好的计算机过程，他取一个或一组的值为输入，并产生一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入的数据转化成输出结果。

        算法可以被看作是一种指导计算机执行特定任务的方法。它们可以用来执行各种操作，例如搜索、排序、数据处理、图形处理等。算法通过定义逻辑和控制流程来实现特定的计算目标。

一个好的算法应该具有以下特点：

1. 正确性：算法应该能够正确地解决给定的问题。
2. 效率：算法应该以尽可能少的时间和资源完成任务。
3. 可读性：算法应该易于理解和实现。
4. 可维护性：算法应该易于修改和调试。

        常见的算法包括排序算法（如冒泡排序、快速排序）、搜索算法（如线性搜索、二分搜索）、图算法（如最短路径算法、最小生成树算法）等。

3.算法效率

既然提起算法我们就得要考虑算法的效率，那么算法的效率该如何判断呢？

3.1如何衡量一个算法的好坏

首先，我们先观察下列代码

long long Fib(int N)
{
	if (N < 3)
		return 1;
 
	return Fib(N - 1) + Fib(N - 2);
 
}

我们知道斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？

那该如何衡量好坏呢？

衡量一个算法的好坏通常涉及以下几个方面：

1. 正确性：算法应该能够正确地解决给定的问题。通过测试算法在各种情况下的输出和预期结果是否一致，可以评估算法的正确性。

2. 时间复杂度：算法的时间复杂度衡量了算法执行所需的时间资源。通常以大O表示法表示，它描述了算法执行时间随输入规模增长的趋势。时间复杂度越低，算法执行所需的时间资源越少，算法越好。

3. 空间复杂度：算法的空间复杂度衡量了算法执行所需的额外空间资源。类似于时间复杂度，空间复杂度也用大O表示法表示。较低的空间复杂度表示算法使用更少的内存空间，即节省了资源。

4. 可读性和可维护性：算法应该易于理解、实现和修改。一个好的算法应该具有良好的代码结构、清晰的命名和注释，以及遵循良好的编程实践。

5. 可扩展性：算法在处理不同规模和类型的输入时应该能够保持良好的性能。一个好的算法应该能够适应不断增长的数据量，并且在不同场景下都能够有效地工作。

3.2算法的复杂度

        算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

        时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法的运行所需要的额外空间。在计算机发展的早期，计算机的尺寸容量很小。所以空建复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的储存容量已经达到了很高的程度。所以我们如今不再需要特别关注一个算法的空间复杂度。

4.时间复杂度

4.1时间复杂度的概念

        时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

计算时间复杂度是评估算法执行时间随输入规模增长的趋势。以下是一些常见的计算时间复杂度的方法：

1. 计算基本操作次数：首先，分析算法中的基本操作，例如赋值、比较、算术运算等。然后，根据输入规模，计算这些基本操作的执行次数。

2. 忽略常数项和低阶项：在计算时间复杂度时，通常忽略常数项和低阶项。因为当输入规模非常大时，这些项对于总体的增长趋势来说并不重要。

3. 使用大O表示法：时间复杂度通常使用大O表示法来表示。它描述了算法执行时间与输入规模增长的关系。例如，O(1)表示常数时间复杂度，O(n)表示线性时间复杂度，O(n^2)表示平方时间复杂度等。

4. 分析循环结构：对于包含循环结构的算法，需要分析循环的迭代次数。通常使用迭代变量和循环条件来计算循环的次数，并结合基本操作次数计算总体复杂度。

5. 分析递归结构：对于递归算法，可以使用递归方程来计算时间复杂度。递归方程描述了问题规模的变化，并根据递归的深度和基本操作次数计算总体复杂度。

我们看下面列子：

//请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
	int count = 0;
	int i = 0;
	for (i = 0;i < N;i++)
	{
		int j = 0;
		for (j = 0;j < N;j++)
		{
			++count;
		}
	}
 
	int k = 0;
	for (k = 0;k < 2 * N;++k)
	{
		++count;
	}
 
	int M = 10;
	while (M--)
	{
		++count;
	}
 
	printf("%d\n", count);
}

Func1执行的基本操作次数：

• N=10        F(N)=130
• N=100      F(N)=10210
• N=1000    F(N)=1002010 

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示方法。

4.2大O的渐进表示法

大O符号（Big O notatio）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则除去与这个项目相乘的常数 ，得到的结果就是大O阶。

使用大O阶的渐进表示法后，Func1的时间复杂度为：

        

• N=10        F(N)=100
• N=100      F(N)=10000
• N=1000    F(N)=1000000 

        通过上面我们发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了 执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏的情况：

最坏情况：任意输入规模的最大运行次数（上界）

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数（下界）

例：在一个长度为N数组中搜索一个数据x

最好情况： 1次找到

最坏情况： N次找到

平均情况： N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间O(N)。时间复杂度计算时，是一个稳健保守预期。

4.3时间复杂度计算举例

实例1

//请计算一下Func2时间复杂度
void Func2(int N)
{
	int count = 0;
 
	int k = 0;
	for (k = 0;k < 2 * N;++k)
	{
		++count;
	}
 
	int M = 10;
	while (M--)
	{
		++count;
	}
 
	printf("%d\n", count);
}

计算可知Func2的基本操作次数：O(N)=2*N+10

再使用大O 渐进表示法后，时间复杂度就为  O(N)

实例2

void Func3(int N, int M)
{
	int count = 0;
	int k = 0;
	for (k = 0;k < M;++k)
	{
		++count;
	}
	
	for (k = 0;k < N;++k)
	{
		++count;
	}
	printf("%d\n", count);
}

计算Func3的基本操次数：O(M+N)

因为M和N都是未知数，所以可以看为O(2N) 再忽略系数

所以Func3的时间复杂度为O(N)

如果前提说了M和N一样大，那么时间复杂度可以是O(M)或O(N)

如果前提说了M大于N，那么时间复杂度是O(M)

如果前提说了M小于N，那么时间复杂度是O(N)

实例3

void Func4(int N, int M)
{
	int count = 0;
	int k = 0;
	for (k = 0;k < 100;++k)
	{
		++count;
	}
 
	printf("%d\n", count);
}

 

Func4的时间复杂度是：O(1)

 实例4

//计算strchr时间复杂度
const char * strchr (const char * str, int character);

观察代码我们可以看到其功能相当于在字符数组中查找一个字符。

所以最好的情况是一次找到，最坏的情况是找N次找到；所以时间复杂度为O(N)

 实例5

 void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
 
		if (exchange == 0)
			break;
	}
}

冒泡排序，可以简单理解为，已知数组是升序排列，现在改为降序

 1 2 3 4 5 6

 6 5 4 3 2 1

就是将数组的相邻两个元素进行比较，如果第一个元素小于第二个元素，就将他们的位置互换。

所以实例5基本操作最好执行N次，最坏执行N*(N-1)/2次，在通过大O阶方法，所以该算法时间复杂度为O(N^2)。

实例6

int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
    //begin和end是左闭右闭区间
	while (begin <= end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
 
	return -1;
}

二分查找最坏的情况是：一直查找直到查找区间缩放的只剩一个值或找不到。

每一次查找相当于在上次查找的基础上除二，所以除了多少次2，就查找了多少次。

最好的一次找到，最坏的情况找O(logN),所以实例6时间复杂度为O(logN)。

 实例7

//计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}

 观察可得递归了N次，所以时间复杂度为O(N)。

5.空间复杂度

        空间复杂度也是一个数学表达式，是对一个算法在运行过程中额外临时占用存储空间大小的量度。

        空间复杂度不是程序占用了多少bytes的空间，因为这个也没有太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需的栈空间（存储参数、局部变量、一些寄存器的信息等）在编译期已经确定好了，因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。

时间是累积的，空间是可以重复利用的。

实例1

//计算BubbleSort的空间复杂度
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
 
		if (exchange == 0)
			break;
	}
}

首先数组的n个空间不算，end、exchange、i都需要开辟额外空间，所以就是使用了常数个额外空间，空间复杂度为O(1)。

实例2

long long* Fibonacci(size_t n)
{
	if (0 == n)
		return NULL;
 
	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
	fibArray[0] = 0;
	fibArray[1] = 1;
	int i = 0;
	for (i = 0;i <= n;i++)
	{
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
 
	return fibArray;
}

 动态开辟了N个空间，空间复杂度为O(N)。