数据结构与算法1

一、概述

数据结构（逻辑结构、存储结构、算法）
数据项 ∈ 数据元素(记录) ∈ 数据。

数据元素（结点）：数据的基本单位。
数据项：不可分割，最小数据单位。
数据对象：性质相同的数据元素的集合，数据的子集。

1、逻辑结构（线性和非线性）

数据结构（相互之间存在一种或多种特定关系的数据元素的集合）

集合：同属于一个集合是数据元素之间的唯一关系。
线性结构：“一对一”关系，仅有一个直接前驱和一个直接后继。
树形结构：”一对多”关系，除根节点外仅有唯一直接前驱，所有结点都可以有0到多个直接后继。
图形结构：”多对多”关系，多个直接前驱和多个直接后继。

2、存储结构

顺序存储（一维数组）
链式存储（链表）
索引存储（索引表）
散列(hash)存储（构造散列函数）

二、时间复杂度

时间复杂度主要衡量的是一个算法的运行次数，而空间复杂度主要衡量一个算法所需要的额外空间

总结：衡量一个算法的好坏，就是从时间和空间两个维度来衡量。

1、时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

// 请计算一下Func1基本操作执行了多少次？
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)    // 第一段
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	for (int k = 0; k < 2 * N; ++k)   // 第二段
	{
		++count;
	}
	int M = 10;
	while (M--)       // 第三段
	{
		++count;
	}
	printf("%d\n", count);
}

Func1函数是有三个循环组成，由上面讲的可以得知，执行了多少次就是我们想要的时间复杂度

第一段嵌套for循坏执行次数是就是 N * N，因为有两层循环，第一层和第二层都是走到N才能停止
第二段for循坏执行次数是 2 * N，因为K = 0 要递增到 2 * N才能停止
第三段while循环执行次数是 10，因为 M = 10，M进入循环递减到0，才能停止

所以F(N) = N² + 2 * N + 10
但是实际中我们计算时间复杂度时，我们并不需要计算准确的执行次数，只需要大概执行次数，这里我们用大O的渐进表示法。

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

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后，Func1的时间复杂度为：O(N²)

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

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

最坏情况：任意输入规模的最多运行次数
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最少运行次数

int FindNum(int *arr, int len, int x) {
	for (int i = 0; i < len; i++) {
		if (arr[i] == x)
			return i;
	}
	return -1;
}
 
int main() {
	int arr[] = { 11,22,33,44,55,66,77,88,99 };
	int len = sizeof(arr) / sizeof(int);
	int f = FindNum(arr, len, 11);		// 最好情况：数组的第一个就找到了
	int m = FindNum(arr, len, 55);		// 平均情况：数组的一半找到了
	int l = FindNum(arr, len, 99);		// 最坏情况：数组的最后才找到
 
	printf("最好情况数组下标：%d\n", f);
	printf("平均情况数组下标：%d\n", m);
	printf("最坏情况数组下标：%d\n", l);
 
	return 0;
}

最好情况：1次就找到

最坏情况：N次找到

平均情况：N/2次找到

但是在实际中一般关注的是算法的最坏运行情况，所以数组中搜索数字时间复杂度为O(N)

2、常见时间复杂度计算举例

1.双重循环

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

k = 0，k要递增到 k = 2 * N，才能结束

m = 10；要执行10次，所以精确执行次数是2N + 10

用大O渐进表示法最后时间复杂度是O(N)

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

第一个for循环k = 0，k < M，需要执行M次才能结束

第二个for循环k = 0，k < N，需要执行N次才能结束

只是在M和N不确定谁大情况下，时间复杂度是O(M + N)

M和N相等，时间复杂度是O(M) 或者 O(N)

M远大于N，时间复杂度是O(M)

N远大于M，时间复杂度是O(N)

2.常数循环

// 计算Func4的时间复杂度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

k = 0，要递增到100的时候循环才能停止

有很多人就觉得结果是O(100)，错误，时间复杂度里面就没有这种说法

我们看到一个明确的次数，都要把它看成O(1)

这里不是循环只跑了1次，而是常数(明确)次数

所以时间复杂度是O(1)

3.str char

// 计算strchr的时间复杂度？
const char* strchr(const char* str, char character)
{
	while (*str != '\0')
	{
		if (*str == character)
			return str;
 
		++str;
	}
 
	return NULL;
}

看最坏情况，要么是找字符串最后一个或者就是没有找到

时间复杂度是O(N)

4.冒泡

// 计算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;
	}
}

冒泡排序很多人都知道时间复杂度是O( $N^{2}$ )，我们来来它是怎么来的呢

错误想法：不要看有x个循环套着，就是O( $N^{x}$ )

我们需要分析循环的执行条件

要对N - 1个进行排序，每次还需要交换N - 1，N - 2，N - 3，…… 2 ，1

我们把次数相加，等等这怎么有点像等差数列,公差是1,首项是N - 1,尾项是1,项数是N -1

现在我们就可以用数列的求和公式： $\frac{(N-1)+1*(N-1))}{2}$

省略掉不重要的项数，大O渐进表示法O( $N^{2}$ )

最好情况是O(N)

如：2,1,3,4,6,5，只需要交换N - 1次

5.二分查找

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n;
	while (begin < end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return -1;
}

二分查找的最好情况是O(1)，折半第一次的时候的正好就找到了

最坏情况是找最左边或者最右边，还有就是找不到

N / 2 / 2 / …… / 2 = 1

折半了几次，就是查找了几次

设折半了x次
$2^{x}=N$ , $x = {log_{2}}^{N}$

所以时间复杂是O( ${log_{2}}^{N}$ )

6.递归

// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N)
{
 return N < 2 ? N : Factorial(N-1)*N;
}

递归算法：递归次数 * 每次递归调用的次数

递归了N次，每次调用了2次，其中比较了1次，还有最后return的时候计算了1次，所以是常数次，所以是N * 常数次，还是O（N）

N * (N - 1) * (N - 2) * (N - 3) ...... * 1 ，逐步向下递归，递归了N次

时间复杂度是O(N)

// 计算斐波那契递归Fib的时间复杂度？
long long Fib1(size_t N) 
{
    if(N < 3)
        return 1;
    return Fib(N-1) + Fib(N-2);
}

时间复杂度即O( $2^{N}$ )

俺们期末不咋考这个，过一遍即可

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/724116.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！