时间复杂度

大家好，想必大家都知道衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，我们今天来分享数据结构的时间复杂度。

算法的复杂度：衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

时间复杂度的概念：

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

接下来看到下面的代码：

// 请计算一下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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

我们看到代码，这段代码一共执行了(N^2+2*N+10)次对吧，大家觉得我们这段代码的时间复杂度是多少呢？这段代码的时间复杂度为O(N ^2)，那么为什么是这个呢，接下来我们就详细的了解一下。

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

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

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

那我们上面的这段代码的时间复杂度是多少是不是就迎刃而解了呢。但是呢我们还有一个点需要注意，在实际中一般情况关注的是算法的最坏运行情况，看到下面的例子我相信大家一定可以理解的。

例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
1
2
3
4

如果在这种情况下我们的时间复杂度又是多少呢？最坏的情况来考虑的话就是O(N)。

熟能生巧，我们看看接下来的例题的时间复杂度是多少吧：

// 计算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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们代码的执行次数是2*N+10，那我们的时间复杂度就是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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这里的话得分情况：
不确定M和N的情况下：O(M+N)
N远大于M：O(N)
M远大于N：O(M)

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

1
2
3
4
5
6
7
8
9
10
11

我们规定O(1)不是代表1，而是常数次，所以我们这里的时间复杂度就是O(N)。

// 计算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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

最好情况：只在第一次循环就完成了，在第二层循环就是执行N-1次，那么这种情况下的时间复杂度就是O(N)。
最坏情况：一直到执行完了才排序完成，第一层为n时，那么第二层循环就是执行n-1次，然后第一层为的end等于n-1，第二层循环执行n-2次，这里就可以看得出来这里是等差数列求和了，求出来根据我们的规则那么这个题的时间复杂度就是O(N^2)。

这里我们通过力扣网的题来实操一下：

思路一：先给这个数组冒泡排序，在经过一次遍历来解决问题，如果当前值加1不等于下一个数，那么消失的数字就是当前值+1。
思路二：我们利用两个数组，将我们输入的数字全部异或起来，还有就是将我们另外一个数组里完整的数字也异或起来，因为异或的规则是相同为0，不同为1，而且异或操作符满足交换律，所以通过异或操作符就可以解决了。
思路三：通过等差数列求和，依次减去缺失数字的数组里的数，得到就是我们想要的结果了。

因为我们的题要求我们的时间复杂度为O(N），所以我们只能用思路二和思路三进行解题。

//思路二：
int missingNumber(int* nums, int numsSize) {
    int x = 0;
    int i = 0;
    for (i = 0; i < numsSize;++i)
    {
        x ^= nums[i];
    }
    for (i = 0; i <= numsSize; ++i)
    {
        x ^= i;
    }
    return x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//思路三：
int missingNumber(int* nums, int numsSize) {
   int N=numsSize;
   int sum=(0+N)*(N+1)/2;
   for(int i=0;i<numsSize;++i)
   {
       sum-=nums[i];
   }
   return sum;
}
1
2
3
4
5
6
7
8
9
10

今天的分享就到这里了，谢谢大家。