数据结构入门篇：第一篇

🤔首先，为什么要学数据结构？

数据结构的概念：在内存中对数据进行管理；
数据结构的学习能让我们在处理大量数据时提高处理效率，即让我们在不同的场景下更快的处理大量数据；

🤔算法和数据结构有什么关系？

算法就是处理数据的一种方法；
数据结构是为算法服务的，算法作用在特定的数据结构之上，而衡量数据结构和算法好坏的标准就是复杂度，即时间复杂度和空间复杂度；

1.时间复杂度

🤔什么是时间复杂度？

时间复杂度是衡量算法的快慢；

🤔🤔那么我们能不能把算法放到电脑上跑一跑，记录一下时间？

这样比较是很难比较出来算法的好坏，但又因为一个算法的语句执行次数与它所花费的时间成正比，所以我们把语句大概执行次数作为衡量一个算法的时间复杂度；

👉算法时间复杂度的定义👈

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

// 请计算一下Func1中++count语句总共执行了多少次？
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);
}

这里很容易算出这个数学表达式：F(N)=N² +2*N+10;
Func1 执行的基本操作次数 ：

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

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

🤔🤔🤔什么是大O的渐进表示法？

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

大O的渐进表示法的规则：

1. 如果一个算法的语句执行的次数是一个常数，那么可以表示为O(1);
2. 如果一个算法的语句执行次数是一个高阶函数，那么只保留最高阶项；
3. 如果最高阶项存在且不是1，则去除这个项的系数。得到的结果就是大O阶。
4. 如果一个算法有最好，最坏，平均三种情况，那么取最坏的情况；

总的来说就是要忽略对结果影响不是很大的项。

2.时间复杂度的练习

problem one:

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);
}

• 数学表达式：2*N+10
• 时间复杂度（大O的渐进表示法）：O(N)

problem two:

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);
}

• 数学表达式：M+N
• 时间复杂度（大O的渐进表示法）：O(M+N)，这里M和N并没确定关系，所以是M+N；

problem three：

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

• 数学表达式：100
• 时间复杂度（大O的渐进表示法）：O(1)

problem four：

void Swap(int* p,int* q)
{int tmp=*p;*p=*q;*q=tmp;
}
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-1
  最坏情况：逆序，（N*(N-1)）/2
• 时间复杂度：取最坏情况，O(N²);

problem five:

int BinarySearch(int* a, int target, int x)
{assert(a);int left = 0;int right = target-1;// [begin, end]：begin和end是左闭右闭区间，因此有=号while (left <= right){int mid = (left + right)/2;if (a[mid] < x)left = mid+1;else if (a[mid] > x)right = mid-1;elsereturn mid;}return -1;
}

以上是二分查找的代码；

• 数学表达式：
  最好的情况下，在中间找到，即1
  最坏的情况是一直找找到只剩一个数，即N/2/2/2/2/2/…/2=1；

• 时间复杂度运算过程：设x为大概的执行次数，即2^x=N,那么解出x=logN，即时间复杂度是O(logN),：logN在算法分析中表示是底数为2，对数为N。

problem six:

long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}

• 数学表达式：N+1
• 时间复杂度：O(N)

problem seven:

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

• 数学表达式：2ⁿ-1-x
• 时间复杂度：O(2^N)

总结

以上就是本篇的所有内容了，今天主要学习了时间复杂度的计算，如果喜欢本篇不妨留个❤️；