您现在的位置是:首页 >学无止境 >算法的时间复杂度和空间复杂度网站首页学无止境

算法的时间复杂度和空间复杂度

是小刘同学啦 2024-08-14 00:01:02
简介算法的时间复杂度和空间复杂度

目录

本章重点

一 时间复杂度

2.1 时间复杂度的概念

2.2 大O的渐进表示法

2.3 常见的时间复杂度的计算

二 空间复杂度

三 常见复杂度对比

四 复杂度的oj练习

4.1 消失的数字

4.2 旋转数字


每一天都是人生限定,每一天都值得100%努力


本章重点

(1)算法效率(2)时间复杂度(3)空间复杂度(4)常见的时间复杂度以及复杂度oj练习


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

一 时间复杂度

2.1 时间复杂度的概念

  算法的时间复杂度是一个函数(指的是数学函数),算法中的基本操作的执行次数,为算法的时间复杂度。

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	//N*N
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	//2*N
	int M = 10;
	while (M--)
	{
		++count;
	}
	//M=10
	printf("%d
", count);
}

(1)时间复杂度表达式为:F(N) = N*N+2 * N + 10
(2)大O渐进表示法:O(N^2)

这个函数的基本操作次数是:F(N) = N*N+2 * N + 10,随着N的增大,后两项对整个影响的结果变可以忽略不计小。当N无限大的时候,后两项对结果的影响

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

2.2 大O的渐进表示法

O 符号( Big O notation ):是用于描述函数渐进行为的数学符号。
推导大 O 阶方法:
1 、用常数 1 取代运行时间中的所有加法常数。
2 、在修改后的运行次数函数中,只保留最高阶项。
3 、如果最高阶项存在且不是 1 ,则去除与这个项目相乘的常数。得到的结果就是大 O 阶。

4.另外有些算法的时间复杂度存在最好、平均和最坏情况: 最坏情况:任意输入规模的最大运行次数(上界) ;平均情况:任意输入规模的期望运行次数 ;最好情况:任意输入规模的最小运行次数(下界);在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

2.3 常见的时间复杂度的计算

代码一:

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

时间复杂度为O(1)【因为大O的渐进表示法的第一条用常数1取代运行时间中的所有加法常数】(我们可以看到执行次数为100)(所以,看到大O的渐进表示法,并不是让我们只能执行一次)(常数都是1)

代码二:

void Func2(int N)
{
 int count = 0;
 for (int k = 0; k < 2 * N ; ++ k)
 {
 ++count;
 }
 int M = 10;
 while (M--)
 {
 ++count;
 }
 printf("%d
", count);
}

时间复杂度为O(N)[大O的渐进表示法,第三条:如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。【实际的执行次数是:2*N+10】

代码三:

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
", count);
}

时间复杂度为O(N+M);如果给出N远大于M,就可以写成O(N);如果给出N和M差不多就可以写成O(N)或者O(M);该代码什么都没有给,所以就是O(M+N);

代码4

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

时间复杂度为O(N);因为不确定什么时候被找到,第四条:在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

关于时间复杂度,我们要准确分析时间复杂度,一定要去看思想,不能仅仅去看程序是几层循环,主要是要看代码的思想。比如:冒泡排序(O(N^2)),就是N-1,N-2,N-3……2,1,是一个等差数列(N-1+1)(N-1)/2=N(N-1)【这是最差情况】,N-1【最好的情况】。

二分查找的时间复杂度:O(㏒₂N )【最好的情况:O(1)一次找到;  最差的情况(找不到的情况):O(log2 N )   (1*2*2*2…2)^X(次)= N(从找不到的时候,向前思想】

时间复杂度,会把O(㏒₂N)简写成O(logN).有些书籍也会写成O(lgN)(这个是不正规的)

代码5

long long Fac(size_t N)
{//阶乘
	if (0 == N)
		return 1;

	return Fac(N - 1) * N;
}

时间复杂度为O(N),;实际上是N+1

代码6

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	for (size_t i = 0; i < N; ++i)
	{
		printf("%d", i);
	}
	printf("
");

	return Fac(N - 1) * N;
}

时间复杂度为O(N^2),;实际上是(N-1)+(n-2)+……+1+0

递归算法的时间复杂度:1、每次函数调用如果是是O(1),那么就看他的递归次数(递归次数是多少,时间复杂度就是多少)(代码5)

2、如果不是O(1),那么就看他的递归调用次数的累加(每次递归,函数调用的累加)(代码6)

代码7

long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}
//斐波那契数列
//符合递归算法的第一种

 时间复杂度为O(2^N),第一层调用一次,第二层 调用2次,第三层调用4次 ,一直到Fib(3)分成Fib(2)+Fib(1),那就是N-1层(假设每一层都是满的,起始并不是每一层都是满的),那最后一层就是2^(N-1),然后就是等比数列相加,就是(2^n-1)-1,

二 空间复杂度

空间复杂度 也是一个数学表达式,是对一个算法在运行过程中 临时占用存储空间 大小的量度 。
空间复杂度算的是 变量的个数, 空间复杂度计算规则基本跟实践复杂度类似,也使用 O 渐进表示法 。 注意:函数运行时所需要的栈空间 ( 存储参数、局部变量、一些寄存器信息等 ) 在编译期间已经确定好了,因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定
代码一:
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(1),临时占用储存空间的变量有i、exchange、end,一共三个。

代码2

long long* Fibonacci(size_t n)
{
	if (n == 0)
		return NULL;

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

空间复杂度为O(N),临时占用储存空间有指针开辟的空间n+1个,指针fibArray,i;一共n+3个

代码3

long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}
空间复杂度为O(N), 递归调用了N 次,开辟了 N 个栈帧,每个栈帧使用了常数个空间。空间复杂度为 O(N)
代码4
long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

时间复杂度为O(2^N),空间复杂度为O(N),会误认为空间复杂度也是O(2^N),但是递归的调用的函数,调用完之后就销毁了,把空间还给系统了,下次调用的时候,再次开辟,空间又被使用,空间是可以重复利用。所以仍然是那一份空间。(局部变量存在栈上面,函数结束,局部变量也就销毁了)

知识点:时间一去不复返,是累积的,空间回收以后,可以重复利用。

三 常见复杂度对比

一些常见的复杂度

四 复杂度的oj练习

4.1 消失的数字

数组nums包含从0n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。(时间复杂度为O(N)

输入:[3,0,1]输出:2; 

思路一:先排序,然后进行遍历(冒泡O(N^2),看是否是前一个数字+1得到的值(但是时间复杂度不符合题意)

思路二:映射方式(首先定义一个数组,里面的值全部赋值成-1,然后输入的数组,每一个值是多少,就作为下标对应的位置写多少)(时间复杂度为:O(N))

思路三:异或(用一个val和0-N的数字异或,再和数据中的数字异或,最后cal中得知就是缺失的值)(O(N))

思路三:等差数列(O(N))

代码1展示:(思路三)函数接口型

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

}

4.2 旋转数字

给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。输入: nums = [1,2,3,4,5,6,7], k = 3输出: [5,6,7,1,2,3,4]解释:向右轮转 1 步: [7,1,2,3,4,5,6]向右轮转 2 步: [6,7,1,2,3,4,5]向右轮转 3 步: [5,6,7,1,2,3,4]

思路一:右旋K次(每次右旋一次)【时间复杂度为O(N*K);空间复杂度为O(1)】(时间复杂度的k最大为N-1),最坏的结果为O(N^2))

思路二:开设一个新的数组,把后k个放到新数组的前面,前面的依次放到后面【时间复杂度O(N),空间复杂度O(N)】 (这种方法比第一种,就是时间换取空间的算法)

思路三:三趟逆置【时间复杂度为O(N),空间复杂度为O(1)】

(思路一和思路三在C语言进阶栏目-C进阶习题里面有详细说明 http://t.csdn.cn/sFLCM

思路三:(函数接口型)

void reverse(int* arr,int left, int right)
{
    while (left < right)
    {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        ++left;
        --right;
    }
}
void rotate(int* nums, int numsSize, int k){
    int m = k % numsSize;
    reverse(nums, 0, numsSize - m - 1);
    reverse(nums, numsSize - m, numsSize - 1);
    reverse(nums, 0, numsSize -1);
}

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。