时间(空间)复杂度(结构篇)

简介: 时间(空间)复杂度(结构篇)

复杂度是计算机科学中的一个基础概念,它帮助我们理解和评估算法的效率,对于算法设计和优化至关重要。算法的复杂度通常分为时间复杂度和空间复杂度两个方面。

前言:

众所周知:程序 = 算法  + 数据结构;衡量一个算法的标准就是算法效率。那么,算法效率是指算法执行的时间和所需的存储空间。在计算机科学中,算法效率通常通过时间复杂度空间复杂度来衡量。

一、时间复杂度

1.1 时间复杂度的定义

  • 时间复杂度是衡量算法执行时间随输入规模增长而变化的度量,它指示了算法的效率和性能。
  • 时间复杂度通常使用大O符号(O)来表示,表示算法执行时间的上界。
  • 时间复杂度描述的是算法执行时间与输入规模的增长趋势,而不是具体的执行时间。

1.2 时间复杂度的分析

表示方法:

大O 的表示法:是用于描述函数渐进行为的数学符号。

算法中的基本操作的执行次数,为算法 的时间复杂度。随着问题规模 n 的伴随某个函数f(n)变话记作:  

  • 一般的忽略常数项。
  • 只保留最高次幂项。

注意:我们通常表示的是一个数量级,而不是具体值或某个函数。

1.3 常见的时间复杂度

  • 常数时间复杂度:O(1),表示算法的执行时间不随输入规模的增长而变化,是最理想的情况。
  • 对数时间复杂度:O(log n),通常出现在二分查找等分治算法中。
  • 线性时间复杂度:O(n),表示算法的执行时间与输入规模成正比。
  • 线性对数时间复杂度:O(n log n),通常出现在快速排序、归并排序等分治算法中。
  • 平方时间复杂度:O(n^2),通常出现在嵌套循环的算法中。
  • 指数时间复杂度:O(2^n),通常出现在递归算法中。
  • 多项式时间复杂度:O(n^k),k可能是大于 2 的正整数,这意味着算法在大规模数据上的性能下降较快。

1.4 时间复杂度的计算以及简单的分析

通过分析算法中基本操作的执行次数,并根据输入规模的增长情况确定时间复杂度。

三种情况:

  • 最好时间复杂度
  • 平均时间复杂度
  • 最坏时间复杂度
冒泡排序
// 计算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;
     }
}

分析:冒泡排序的时间复杂度:O(N^2)

解释:有N个个数,每次移动N-1次,剩下(N-1)移动(N-2)次,总共执行(N*(N-1)/2)次,根据大O表示就是:

折半查找(二分查找)
// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
    assert(a);
 
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {
        int mid = begin + ((end - begin) >> 1);
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid;
        else
            return mid;
    }
 
    return -1;
}

分析:折半查找的时间复杂度:最好是O( 1 ) ,最坏是O( log N ) ,该式表示:以2为底N的对数(仅限在计算机中表示)

解释:在查找的时候每次折半,也就是除以 2,一次是2^1,两次是 2^2,推广到N次数。

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

分析:斐波那契数列时间复杂度:O(2^n)

解释:

二、空间复杂度

2.1 空间复杂度的定义

  • 空间复杂度(Space Complexity)是衡量算法在执行过程中临时占用存储空间大小的量度。
  • 它反映了算法所需存储空间与输入数据大小之间的关系。
  • 空间复杂度通常用大O表示法来表示。

2.2 空间复杂度的分析

同时间复杂度一样用大O表示法表示;也是表示一个数量级。记作:

2.3 常见的空间复杂度

  • 常数阶:如果算法的空间复杂度不随问题规模 n 的变化而变化,即算法所需的存储空间是一个常数,那么空间复杂度为 O(1)。
  • 线性阶:如果算法所需的存储空间与问题规模 n 成正比,即算法所需的存储空间随着 n 的增加而线性增加,那么空间复杂度为 O(n)。
  • 多项式阶:如果算法所需的存储空间与问题规模 n 的关系可以表示为多项式函数,即空间复杂度为 O(n^k),其中 k 是一个正整数。
  • 对数阶:如果算法所需的存储空间与问题规模 n 的关系可以表示为对数函数,即空间复杂度为 O(log n)。
  • 指数阶:如果算法所需的存储空间与问题规模 n 的关系可以表示为指数函数,即空间复杂度为 O(2^n)。

2.4 空间复杂度的计算以及简单分析

计算空间复杂度时,需要考虑算法在运行过程中显式申请的额外空间,而不是函数运行时所需要的栈空间,后者在编译期间已经确定好了

冒泡排序
// 计算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;
     }
}

分析:冒泡排序空间复杂度:O(1)

解释:仅仅使用了一个额外变量。

斐波那契数列(迭代)
// 计算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;
}

分析:斐波那契数列空间复杂度:O( N )

解释:开辟了N个空间。

目录
相关文章
|
2月前
|
算法 C++ 开发者
Pythoner必看!复杂度分析:时间VS空间,你的代码为何跑得慢?深度揭秘!
在Python编程中,每位开发者都希望代码能快速执行。然而,有时候代码运行缓慢,令人困惑。本文将深入解析时间复杂度和空间复杂度,帮助你找到性能瓶颈。时间复杂度衡量算法执行时间随输入规模的增长情况,而空间复杂度关注算法所需的额外内存空间。两者是评估算法性能的核心指标。例如,线性搜索的时间复杂度为O(n),二分搜索为O(log n),但它们的空间复杂度均为O(1)。通过选择高效算法和数据结构,以及减少不必要的变量分配,可以有效优化代码性能。掌握这些技巧,有助于提升程序速度和稳定性。
52 1
|
3月前
|
机器学习/深度学习 存储 算法
【初阶数据结构篇】时间(空间)复杂度
复杂度是计算机科学中的一个基础概念,它帮助我们理解和评估算法的效率,对于算法设计和优化至关重要。
43 2
【初阶数据结构篇】时间(空间)复杂度
|
4月前
软件复杂度问题之根据统计的运算子和运算元数据计算Halstead复杂度,如何解决
软件复杂度问题之根据统计的运算子和运算元数据计算Halstead复杂度,如何解决
|
5月前
|
存储 算法
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
101 0
|
6月前
|
存储 算法 数据管理
C++中利用随机策略优化二叉树操作效率的实现方法
C++中利用随机策略优化二叉树操作效率的实现方法
116 1
位图算法(空间换时间)
位图算法(空间换时间)
|
算法
一篇文章带你整体了解算法中的基本问题《查找》
查找 本章对算法中的基本问题--查找做了一个简要介绍,包含了一些基本算法思想以及评价,后续文章详细介绍一些算法,欢迎关注本系列。 可以转载,但请声明源链接:文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)
74 0
|
存储 机器学习/深度学习 自然语言处理
【算法的特性,标准,时间维度空间维度计算方式】
【算法的特性,标准,时间维度空间维度计算方式】
284 0
【算法的特性,标准,时间维度空间维度计算方式】
|
算法
分析复杂度来判断算法效率
算法复杂度用于分析算法运行所需计算机资源的量,需要的时间资源为时间复杂度,需要的空间资源为空间复杂度。 在判断一个算法的优劣时,可以抛开软件和硬件因素,只考虑问题的规模。编写程序前预先估计算法优劣,可以改进并选择更高效的算法。
150 0
分析复杂度来判断算法效率