【海贼王的数据航海：利用数据结构成为数据海洋的霸主】时间复杂度 | 空间复杂度

目录

1 -> 算法效率

1.1 -> 如何衡量一个算法的好坏？

1.2 -> 算法的复杂度

2 -> 时间复杂度

2.1 -> 时间复杂度的概念

2.2 -> 大O的渐进表示法

2.3 -> 常见时间复杂度计算

3 -> 空间复杂度

4 -> 常见复杂度对比

1 -> 算法效率

1.1 -> 如何衡量一个算法的好坏？

对于以下斐波那契数列：

#define _CRT_SECURE_NO_WARNINGS
#include 
using namespace std;
long long fib(int N)
{
	if (N  
用递归实现斐波那契数列，看上去代码十分简洁，但简洁一定就是好算法吗？如何衡量一个算法的好坏？
 
1.2 -> 算法的复杂度
 
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
 
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机存储容量很小。所以对于空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要特别关注一个算法的空间复杂度。
 
2 -> 时间复杂度
 
2.1 -> 时间复杂度的概念
 
定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上来讲，是不能算出来的，只有把程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗？固然可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方法。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
 
即：找到某条语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
 
#define _CRT_SECURE_NO_WARNINGS
#include 
using namespace std;
// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i   
  N = 1000 F(N) = 1002010  
  
 
实际我们在计算时间复杂度时，并不一定要计算精确的执行次数，只需要大概执行次数，所以我们使用大O的渐进表示法。
 
2.2 -> 大O的渐进表示法
 
大O符号(Big O notation)：是用于描述函数渐进行为的数学符号。
 
推导大O阶方法：
 
在常数1取代运行时间中的所有加法常数；
在修改后的运行次数函数中，只保留最高阶项；
如果最高阶项存在且不为1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法后，Func1的时间复杂度为：
 
 
 
 
 
-> N = 10 F(N) = 100 
 
  
  ->  
  N = 100 F(N) = 10000  
  
  
  ->  
  N = 1000 F(N) = 1000000 
  
 
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。 
 
另外有些算法的时间复杂度存在最好、平均和最坏情况：
 

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

  例如：在一个长度为N的数组中搜索一个数据x

  • 最好情况：1次找到
  • 平均情况：N / 2次找到
  • 最坏情况：N次找到

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

    

    2.3 -> 常见时间复杂度计算

    实例1：

    // 计算Func2的时间复杂度？
    void Func2(int N)
    {
    	int count = 0;
    	for (int k = 0; k  a[i])
    			{
    				Swap(&a[i - 1], &a[i]);
    				Exchange = 1;
    			}
    		}
    		if (exchange == 0)
    			break;
    	}
    }

    实例2：

    // 计算fib的空间复杂度？
    // 返回斐波那契数列的前n项
    long long* fib(size_t n)
    {
    	if (n == 0)
    		return NULL;
    	long long* arr = (long long*)malloc((n + 1) * sizeof(long long));
    	arr[0] = 0;
    	arr[1] = 1;
    	for (int i = 2; i  常见复杂度对比 
    一般算法的常见复杂度：
     
    

    5201314	O(1)	常数阶
    3n + 4	O(n)	线性阶
    3n ^ 2 + 4n + 5	O(n ^ 2)	平方阶
    3log(2)n + 4	O(logn)	对数阶
    2n + 3nlog(2)n + 4	O(nlogn)	nlogn阶
    n ^ 3 + n ^ 2 + 3n + 4	O(n ^ 3)	立方阶
    2 ^ n	O(2 ^ n)	指数阶

    

    ---

    感谢大佬们支持！！！

    互三啦！！！