算法的时间复杂度

发布于：2024-05-08 ⋅ 阅读:(20) ⋅ 点赞:(0)

今日备忘录: 不知道什么是命运, 才知道命运是什么.

文章索引

前言

博客主页: 酷酷学!!!

本文将进行算法时间复杂度的分析, 期待更多文章, 感谢关注

正文开始

算法效率

如何衡量一个算法好坏呢?

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

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

如下: 复杂度在校招中的考察

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

时间复杂度

1. 时间复杂度的概念

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

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

例如:

// 请计算一下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);
}

在这里插入图片描述
实际中我们计算时间复杂度, 我们其实并一定要计算精确的执行次数, 而只需要大概的执行次数, 那么这里我们使用大O的渐进表示法.

2. 大O的渐进表示法

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

推导大O阶方法:

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

使用大O的渐进表示法后, Func1的时间复杂度为: O(N^2)

在这里插入图片描述
通过上面我们会发现大O渐进表示法去掉了那些对结果影响不大的项, 简洁明了的表示出了执行次数.

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

  • 最坏情况: 任意输入规模的最大运行次数(上界)
  • 平均情况: 任意输入规模的期望运行次数
  • 最坏情况: 任意输入规模的最小运行次数(下界)

例如:

在一个长度为N的数组中搜索一个数据X
最好情况: 1次找到
最坏情况: N次找到
平均情况: N/2次找到

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

3. 示例

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

分析:
实例1基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N)

实例2

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

分析:
实例2基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)
或者O(MAX(M,N)) 如果M远大于N,O(M), 如果N远大于M,O(N).

实例3

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

分析: 实例3基本操作执行了10次，通过推导大O阶方法，时间复杂度为 O(1)

实例4

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

分析:这里我们可以模拟实现一下strchr

char* my_strchr(const char* str, int character)
{
	while (*str)
	{
		if (*str == character)
			return str;
		else
			++str;
	}
	return NULL;
}

实例4基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为 O(N)

实例5

// 计算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-1 + N-2 + … + 2 + 1,即为等差数列N*(N-1)/2
大O表示法O(N^2)

实例6

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
	assert(a);

	int begin = 0;
	int end = n - 1;
	// [begin, end]：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;
}

分析: 二分查找的时间复杂度

在这里插入图片描述

查找区间的变化:

N
N/2
N/4
N/8
…
1

分析最坏的情况, 也就是查找区间只剩一个数字,或者找不到,也就是
N/2/2/2…/2 = 1, 查了多少次也就是除了多少2
那我们假设查找次数为X, 2^X = N
则查找次数为X = logN,底数2忽略不写
故时间复杂度O(logN)
因为写的时候需要支持专业公式, 否则不好写底数,时间复杂度当中, 为了方便,可以忽略底数,但是其他地鼠不可以忽略, 但也很少出现

实例7

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

	return Fac(N - 1) * N;
}

分析: 递归函数调用的时间复杂度, 即所有递归调用次数的累加和,
通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。

在这里插入图片描述
拓展:

在这里插入图片描述
如果在其中加一个循环呢?

分析:
每一层循环调用执行次数为N, 其中N也在随之变化,等差数列累加求和, 最后为O(N^2)
在这里插入图片描述

实例8


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

	return Fib(N - 1) + Fib(N - 2);
}

分析:如图所示, 每层递归调用都是以2倍数增长,累加求和,使用等比数列错位相减法

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
通过计算分析发现基本操作递归了2 ^ N次，时间复杂度为O(2 ^ N), 那么这种算法基本废了, 只有理论意义，实践中太慢了.

那么如何解决呢? 这里可以采用循环,复杂度为O(N)

unsigned long long Fib(size_t N)
{
	unsigned long long f1 = 1;
	unsigned long long f2 = 1;
	unsigned long long f3 = 0;
	for (size_t i = 3; i <= N; i++)
	{
		f3 = f1 + f2;
		f1 = f2;
		f2 = f3;
	}

	return f3;
}

这里N的范围最大也就unsigned long long,否则就需要采用大数运算来解决.

复杂度OJ练习

题目一: 消失的数字

OJ链接: 消失的数字

在这里插入图片描述
思路一: 可以先进行排序, 在依次查找, 如果下一个值不等于前一个+1, 下一个值就是消失的数字, 但是如果使用排序算法, 快排qsort 的时间复杂度也为O(N*logN),不符合题目要求.
思路二: 求和0到N,在依次减去数组中的值, 剩下的那个值就是消失的数字, 累加的时间复杂度为O(N),但是数组元素全部相加, 很容易溢出.
代码如下

在这里插入图片描述

思路三: 异或, 把数组的中元素和0到N的元素全部进行异或, 相同为0,不同为1,最后的那个数字就是消失的数字,也不会有溢出风险

代码如下:

int missingNumber(int* nums, int numsSize){
    int x = 0;
    for(int i = 0;i<numsSize;i++)
    {
        x = x^nums[i];
    }
    for(int j = 0; j<=numsSize;j++)
    {
        x = x^j;
    }
    return x;
}

题目二: 旋转数组

OJ链接: 旋转数组

在这里插入图片描述

真实的旋转次数为K%=N

思路一: 先写出旋转一次的函数, 在进行K次的调用

代码如下
在这里插入图片描述
但是会发现报错超出时间限制

在这里插入图片描述
我们分析一下时间复杂度, 最坏情况: K%N等于N-1,也就是O(N^2), 最好情况: K%N等于0
时间复杂度为: O(N^2)

思路二:使用三次逆转法，让数组旋转k次

  1. 先整体逆转
  2. 逆转子数组[0, k - 1]
  3. 逆转子数组[k, size - 1]
void reverse(int* nums, int left, int right)
{
    while(left < right)
    {
        int tmp = 0;
        tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}

void rotate(int* nums, int numsSize, int k) {

    k = k%numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

时间复杂度为O(N),当然也可以使用内存函数memcpy来实现
关于内存函数的用法可以参考文章 整数在内存中的存储

总结

时间复杂度是衡量算法性能的重要指标，它描述了算法的运行时间随着输入规模的增加而增长的趋势。通过对时间复杂度进行分析，我们可以估计算法在不同规模下的运行时间，从而选择更优的算法。
感谢关注!!!

完

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布