[数据结构] -- 时间复杂度和空间复杂度

发布于:2024-05-22 ⋅ 阅读:(45) ⋅ 点赞:(0)

🌈 个人主页:白子寰
🔥 分类专栏:C++打怪之路,python从入门到精通,数据结构,C语言,C语言题集👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+),分享更多关于深度学习、C/C++,python领域的优质内容!(希望得到您的关注~) 

目录

​编辑

算法(Algorithm)

算法特点

算法效率

导图

时间复杂度

是什么?

如何使用大O表示法:

示例

举例

样例①

样例②

样例③

样例④

样例⑤

样例⑥

样例⑦

样例⑧

样例⑨

空间复杂度

是什么?

举例

样例①

样例②

样例③

空间复杂度和时间复杂度的区别


 

算法(Algorithm)

在数据结构中,算法是解决问题或执行任务的一系列有序步骤。

它是一种有限的、确定性的、可执行的指令集,用于完成特定的任务,

例如数据的排序、搜索或管理。


算法特点

1. 有穷性:算法必须在执行有限步骤后结束。
2. 确定性:算法的每一步骤都必须有明确的定义,不会导致歧义。
3. 输入:    算法有0个或多个输入,这些输入是算法执行所需的初始数据。
4. 输出:    算法至少有一个输出,表示算法执行的结果。
5. 可行性: 算法的每一步都必须能够通过执行有限次数的基本操作来实现。


算法效率

算法的效率通常通过时间复杂度和空间复杂度来衡量

时间复杂度表示算法执行所需时间与输入规模的关系,

空间复杂度表示算法执行所需的存储空间量。

选择或设计算法时,通常会考虑这些因素以优化性能。



这篇文章要解决的问题

导图



时间复杂度

是什么?

在数据结构中,时间复杂度是衡量算法执行所需时间的一个指标

它描述了算法执行时间随输入数据规模增长的变化趋势

通常用大O符号(Big O Notation)来表示。


如何使用大O表示法:

  1. 确定算法的执行步骤:分析算法中的循环、递归等结构,确定算法的执行步骤。

  2. 评估执行次数与输入规模的关系:确定算法中每一步或每一组步骤执行的次数与输入规模n的关系。

  3. 简化表达式:在大O表示法中,我们通常只保留最高次项,并去掉常数因子和低阶项,因为它们对算法的渐进行为影响较小。

  4. 确定上界:大O表示法关注的是算法性能的上界,即在最坏情况下的性能。

示例

假设有一个算法,其执行步骤可以表示为:

        第一步执行10次  (常数时间操作)

        第二步执行n次    (线性操作)

        第三步执行n^2次(平方操作)

使用大O表示法,我们可以忽略第一步(因为它是常数时间操作),并简化为:

        总时间复杂度:O(n^2)

这意味着算法的时间复杂度是平方级别的,与输入规模的平方成正比。



举例

样例①

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

样例②

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

样例③

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

样例④

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

样例⑤

//计算strchr的时间复杂度:
const char* strchr(const char* str, int character);
//strchr库函数:在str字符数组中查找一个字符

这个的时间复杂度应分三种情况

①最好情况: 第一次就找了

②平均情况: 找的字符在整个的中间

③ 最坏情况: 最后一次才找到

样例⑥

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

 

样例⑦

//计算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个数,找一次范围缩小一半

最好的情况:

缩小第一次就找到了,(也就是这个数在中间值)

时间复杂度为O(1)

最坏的情况:

缩小多少次范围的一半,就找了多少次

设找了x次,所以 2^x = N

x = logN ,最坏的情况时间复杂度为O(logN)

样例⑧

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

 

样例⑨

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

总结: 

递归算法(时间复杂度):每次递归子函数消耗加起来

空间复杂度

是什么?

空间复杂度是一个用于描述算法在执行过程中所使用的额外空间(除了输入数据所占用的空间之外)的量度。

这里的“额外空间”通常指的是算法运行时的内存使用量

所以空间复杂度计算的是变量的个数,也使用大O表示法

举例

样例①

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

 

样例②

//计算Fibonacci的空间复杂度:
//返回斐波那契数列的前n项
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;
}

 

样例③

//计算阶乘递归Fac的空间复杂度:
long long Fac(size_t N)
{
	if (N == 0)
	{
		return 1;
	}
 
	return Fac(N-1)*N;
}

 

空间复杂度和时间复杂度的区别

时间复杂度 空间复杂度
算法执行所需的时间 算法执行所需的额外空间

 ***********************************************************分割线*****************************************************************************
完结!!!
感谢浏览和阅读。

等等等等一下,分享最近喜欢的一句话:

“逆转时间的公式就是珍惜现在”。

我是白子寰,如果你喜欢我的作品,不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力!!! 
好了划走吧。