精华内容
下载资源
问答
  • 时空复杂度

    2021-01-17 11:28:45
    时空复杂度 输入规模 不同的人在不同的场合下,对于输入规模(input scale)的理解可以不同。一般而言,输入规模应当能描述输入所需的空间。例如,如果算法要求输入一条数列(数组),则输入规模n应当是数列的长度。...

    在这里插入图片描述

    时空复杂度
    输入规模
    不同的人在不同的场合下,对于输入规模(input scale)的理解可以不同。一般而言,输入规模应当能描述输入所需的空间。例如,如果算法要求输入一条数列(数组),则输入规模n应当是数列的长度。
    时间复杂度
    时间复杂度(time complexity)是关于输入规模的函数,用于描述算法执行所需要的时间与输入规模的关系。
    一般地,我们开发一个算法,最终都是要将其应用到输入规模极大的场合中的。比如,我们开发一个排序算法,可能在算法的原型形成之前,大都只考虑对几十个、几百个数排序,但之后我们就要将其推广到对几百万甚至几十亿个数排序的情况。所以,一般不考虑算法在处理小规模问题时耗费的时间,而主要关注处理大规模问题时算法的表现。对于小规模的输入,不同算法的效率差异不明显,并且针对小规模的问题做优化耗费的精力相比收益而言是不经济的。而处理很大规模的输入时,效率的些许差异都可以对算法实际的耗时产生巨大影响。因此,通常考察渐进时间复杂度(asymptotic computational complexity),即当输入规模n趋于正无穷大时,算法的运行时间的极限。
    几种记号
    大O记法
    若存在正的常数c和函数f(n),使得对任何正数n均有
    0≤T(n)≤cf(n)
    则f(n)为算法运行耗时T(n)的一个渐进上界,又记为
    T(n)=O(f(n))
    这种记法也称大O记法(Big-O notation)。不难导出大O符号的如下性质:
    █(∀c>0, O(f(n))=O(cf(n))#(1) )
    █(∀a>b>0, O(na+nb )=O(n^a )#(2) )
    此外,也有小o记号,其区别只是将T(n)≤cf(n)改为
    T(n)<cf(n)
    可见,大O符号描述算法执行时间的最坏情况。它告诉我们:对任意的输入规模n,算法的耗时都不超过O(f(n))。有些情况对算法的最坏时间复杂度具有硬性要求。举例来说,对于控制核电站运行、管理或辅助手术的计算机系统而言,不可以用最好情况以及平均情况的时间复杂度作为主要的评判标准。
    大Ω记法
    若存在正的常数c和函数f(n),使得对任何正数n均有
    T(n)≥cg(n)
    则g(n)为算法运行耗时T(n)的一个渐进下界,又记为
    T(n)=Ω(g(n))
    这种记法也称大Ω记法。大Ω记号是对算法执行效率的乐观估计。它告诉我们:对任意的输入规模n,算法的耗时都不低于Ω(g(n))。
    此外,也有小ω记号,其区别只是将T(n)≥cg(n)改为
    T(n)>cg(n)
    大Θ记法
    若f(n)=O(g(n)), f(n)=Ω(g(n)),则记f(n)=Θ(g(n))。大Θ记法是对算法的时间复杂度的定量界定,是对时间复杂度的较为准确的估计:对任何的输入规模n,算法的耗时T(n)都与Θ(g(n))同阶。

    空间复杂度
    除了执行时间的长短,算法所需的存储空间多少也是衡量其性能的一个重要方面,这就是空间复杂度(space complexity)。上述记号也适用于空间复杂度,这里不再重复说明。
    为了更客观的评价算法性能的优劣,原始输入本身所占用的空间通常不计入空间复杂度。
    算法的时间度复杂度一般也会限制空间复杂度不超过某个上界。但是,在对空间要求非常高的应用场景中,或问题的输入规模极为庞大时,仍然需要考察空间效率,并尽力在空间效率方面不断优化。

    展开全文
  • 时空复杂度分析

    2018-10-03 15:31:44
    时空复杂度分析 数据结构和算法要解决的问题就是让代码运行得更快 , 让存储空间占得更少 , 所以时间和空间复杂度的分析是很重要的 . 那么究竟该如何分析 ? 大 O 复杂度表示法 我们经常会看到 O(1) O(n) O(logn) 这些...

    时空复杂度分析

    数据结构和算法要解决的问题就是让代码运行得更快 , 让存储空间占得更少 , 所以时间和空间复杂度的分析是很重要的 .
    那么究竟该如何分析 ?

    大 O 复杂度表示法

    我们经常会看到 O(1) O(n) O(logn) 这些时空复杂度的表示
    其实这就是 大 O 复杂度表示法 , 它并不表示代码执行真正需要的时间 , 而是一种随着数据规模增长的趋势 , 其中 n 就是数据规模的大小 .

    比如 n = 100 , 那么 O(n) 时间复杂度需要的时间可以假设为 100 s , 而 O(logn) 时间复杂度需要的时间就是 10 s , 差距一下就体现出来了 .
    看下面这段代码

    int cal(int n)
    {
        int sum = 0;
        int i = 1;
        for (; i <= n; ++i)
        {
            sum = sum + i;
        }
        return sum;
    }
    

    功能是求 1 - n 的累加和, 假设执行一行代码的时间为一个 run_time

    那么 3 4 两行代码执行用时为 2*run_time

    而 5 7 两行代码都执行了 n 次, 所以需要的时间为 2n*run_time

    于是整个代码运行的时间 T(n) = (2+2*n)*run_time

    从这里我们可以看出, 整个代码运行的时间 T(n) 和每行代码运行的次数 n 成正比

    设 f(n) = 2+2*n , 即每行代码运行次数的总和, 因为我们只是估算一个增长趋势, 而常数和系数不会对增长趋势产生什么影响, 所以可以简写为 f(n) = n

    则有 T(n) = O(f(n)) , 即表示: 代码执行时间T(n)和代码执行次数f(n)成正比

    则上面代码的时间复杂度可以表示为 O(n)

    如何快速估算一段代码的时间复杂度?

    1, 只关注循环执行次数最多的一段代码

    2, 总的复杂度 = 复杂度量级最高的那段代码的复杂度

    3, 嵌套代码的复杂度 = 嵌套内外代码复杂度的乘积

    举几个例子说明一下:

    int cal(int n)
    {
        int sum_1 = 0;
        int p = 1;
        for (; p <= 100; ++p)
        {
            sum_1 = sum_1 + p;
        }
    
        int sum_2 = 0;
        int q = 1;
        for (; q <= n; ++q)
        {
            sum_2 = sum_2 + q;
        }
    
        int sum_3 = 0;
        int i = 1;
        int j = 1;
        for (; i <= n; ++i)
        {
            j = 1;
            for (; j <= n; ++j)
            {
                sum_3 = sum_3 +  i * j;
            }
        }
    
        return sum_1 + sum_2 + sum_3;
    }
    

    这段代码有三个循环

    第一个循环固定执行 100 次

    第二个循环执行 n 次

    第三个双重循环执行 n*n 次

    所以时间复杂度为 O(100 + n + n*n), 省略常数之后为 O(n + n*n)

    但我们一般只关注最高阶, 即时间复杂度为 O(n^2)

    再来看看下面这个代码

    int f(int n)
    {
        int sum = 0;
        int i = 1;
        for (; i < n; ++i)
        {
            sum = sum + i;
        }
        return sum;
    }
    
    int cal(int n)
    {
        int ret = 0;
        int i = 1;
        for (; i < n; ++i)
        {
            ret = ret + f(i);
        }
    }
    

    在cal函数中, 第18行代码执行了n次, 但是它每次都调用了f(int)函数, 在f(int)函数中, 第7行代码要执行n次, 所以第7行代码一共执行了n*n次, 所以函数cal的时间复杂度是O(n^2)

    其实在实际使用中, 时间复杂度的量级就那么几个, 按从小到大排有

    常数级: O(1)

    对数级: O(logn)

    线性级: O(n)

    线性对数级: O(nlogn)

    平方级: O(n^2)

    立方级: O(n^3) . . . O(n^k)

    指数级: O(2^n)

    阶乘级: O(n!)

    对于这些时间复杂度量级, 可以分为两类:多项式量级和非多项式量级

    其中非多项式量级只有: O(2^n)和O(n!)

    我们把时间复杂度为非多项式量级的算法问题称为 NP(非确定多项式)问题, 当数据规模n越来越大时, 非多项式算法的执行时间会急剧增长, 因此时间复杂度为非多项式量级的算法是非常低效的!

    对于O(1)时间复杂度, 只要执行时间不随n增大而增长, 都可以称为O(1)时间复杂度, 也就是说, 只要代码里没有循环和递归, 即使有成千上万行代码, 时间复杂度也是O(1)

    对于O(logn)和O(nlogn), 这是很常见的时间复杂度量级, 同时也是最难分析的

    i = 1;
    while (i <= n)
    {
        i = i * 2;
    }
    

    例如这个代码, i从1开始, 每次增长2倍, 即 2^0, 2^1, 2^2, 2^3 . . . 2^x = n

    x即为第4行代码执行的次数, 可得 x = log2n, 所以这段代码时间复杂度为O(log2n)

    我们把代码变一下

    i = 1;
    while (i <= n)
    {
        i = i * 3;
    }
    

    可以得到时间复杂度为O(log3n)

    其实, 无论底数为多少, 我们记做O(logn), 因为对数之间可以相互转换, 即

    log3n = log32*log2n

    其中 log32是常数, 可以省略.

    还有一种表示时间复杂度O(m+n)

    int cal(int m, int n)
    {
        int sum_1 = 0;
        int i = 1;
        for (; i < m; ++i)
        {
            sum_1 = sum_1 + i;
        }
    
        int sum_2 = 0;
        int j = 1;
        for (; j < n; ++j)
        {
            sum_2 = sum_2 + j;
        }
    
        return sum_1 + sum_2;
    }
    

    因为我们无法预估m和n的大小, 所以时间复杂度记为O(m+n)

    空间复杂度

    相对于时间复杂度, 空间复杂度的分析就容易多了.

    空间复杂度全称是渐进空间复杂度, 表示算法的存储空间和数据规模之间的增长关系

    常用的空间复杂度量级有O(1), O(n), O(n^2)

    void print(int n)
    {
        int i = 0;
        int* a = new int[n];
        for (; i < n; ++i)
        {
            a[i] = i * i;
        }
    
        for (i = n - 1; i >= 0; --i)
        {
            std::cout << a[i] << "\n";
        }
    }
    

    在这个代码中, 我们申请了一个int型变量存储i, 它的大小是固定的, 不随n改变而改变;还申请了一个大小为n的int型数组, 它的大小随n的改变而改变, 所以这个代码的空间复杂度为O(n).

    我们最常见的复杂度量级其实只有五种

    O(1), O(logn), O(n), O(nlogn), O(n^2)

    在这里插入图片描述

    展开全文
  • 算法时空复杂度分析

    2020-09-01 20:29:55
    文章目录算法时空复杂度分析0.为什么要学习算法时空复杂度分析1.理论2.分析方法3.大O复杂度表示法4.多项式量级复杂度5.时间复杂度分析的简单规则6.两种时间复杂度7.常见的时间复杂度8.空间复杂度分析9.不同情况下的...

    算法时空复杂度分析

    0.为什么要学习算法时空复杂度分析

    算法的复杂度估算是计算机中很重要的一块内容,通过复杂度分析我们可以估算程序和算法的运行时间,使用内存,随着输入数据的规模变大的增长规律,从而分析一个算法的优劣

    算法分析在竞赛中的实际意义就是可以通过算法的复杂度分析估计可以得到的分数,以及选择更好的算法。通常初学者常常遇到的问题是自己写了一个暴力算法,却没有算法复杂度的概念,从而也不知道写的是一个暴力算法,也无法理解自己的算法为什么会超时(TLE),超内存(MLE)

    不论在何种环境,我们学习数据结构和算法以及算法的时空复杂度分析的最终目的就是让我们设计出的算法在计算机上运行的速度更快,所用的内存更小

    算法的复杂度分析在许多大牛的的成长路上以及对于写出更加优秀的算法是十分必要的环节

    1.理论

    理论内容取材于维基百科,详见链接

    算法的时间复杂度是一个函数,用于定性描述这个算法的运行时间。这是一个代表算法输入值的字符串的长度函数,时间复杂度常用大O符号表示,不包括这个函数的低阶项和首项系数,使用这种方式的时候,时间复杂度可以被称为是渐进的,即考察输入值大小趋近无穷时的情况,例如一个算法对于任何大小为n(大于n0)的输入,它至少需要5n^3 + 3n的时间来完成,那么这个算法的时间复杂度就是O(n^3)

    2.分析方法

    通常算法时间复杂度分析有如下的两种方法:

    i. 运行后分析

    ​ 这种方法通常是将写出的算法在机器上运行,统计这个算法使用了多少时间和内存,但是这种方法存在缺陷:这种测试方式对机器的依赖性较强,性能比较强的机器相对的运行时间,占用内存当然比较小;同时测试的结果依赖于测试用的数据,例如二分法,很依赖于数据的排列方式和所查找数据的位置,测试得出的结果参考的意义较低

    ii. 运行前分析

    ​ 因为运行后才对算法的时空复杂度进行分析这样的分析方法存在问题,于是我们考虑到在纸上提前模拟计算一个算法所需要的大概的执行时间和占用内存,于是我们用到了大O复杂度表示法

    3.大O复杂度表示法

    ​ 我们从下面的代码来了解大O复杂度表示法:

    #include<map>
    #include<list>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<iomanip>
    #include<cstring>
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    #define R register
    #define LL long long
    #define pi 3.141
    #define INF 1400000000
    using namespace std;
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	for (R int i = 0; i < n; ++i) {
    		for (R int j = 0; j < n; ++j) {
    			printf("%d ", n);
    		}
    	}
    	return 0;
    }
    

    ​ 我这里展示了一个两层循环嵌套的简单的代码,这段代码对于CPU而言需要分三步进行:读取代码和指令数据,计算,输出结果如果学习过汇编的同学可以更能明白这里。

    ​ 我们假设每条代码在CPU上的运行时间为cpu_time,那么我们可以粗略的估计这里使用的时间。

    对于定义n和输出n的步骤,分别需要一个cpu_time,这里需要2 × cpu_time

    对于每一个单层的循环,我们都需要2n个cpu_time,因此循环嵌套的部分需要4n^2 × cpu_time

    循环内的输出函数需要一个cpu_time,因此对于输出我们需要n^2 × cpu_time

    ​ 这样,对于这个程序,我们总的运行时间为:
    T ( n ) = 4 n 2 + n 2 + 2 = 5 n 2 + 2 T(n) = 4n^2 + n^2 + 2 = 5n^2 + 2 T(n)=4n2+n2+2=5n2+2
    ​ 对于我们每一次输入数据,代码执行时间随n的增大而增大,这个公式的系数是CPU执行每一次代码的时间,即我们之前定义的cpu_time,此时我们将上述公式写成大O复杂度表示法即:
    T ( n ) = O ( f ( n ) ) T(n) = O(f(n)) T(n)=O(f(n))
    ​ 其中T(n)表示算法执行的时间,f(n)表示算法执行的总次数,O()表示 T(n) 和 f(n) 的关系,即大O的由来

    因此我们可以将上面的公式换成:
    T ( n ) = O ( 5 n 2 + 2 ) T(n) = O(5n^2 + 2) T(n)=O(5n2+2)
    ​ 但是我们这里的大O复杂度表示法并不需要计算代码的准确执行时间,而是需要表示一种代码的执行时间或者占用内存随着数据规模增长的一个变化趋势这里需要的不是准确时间,而是变化趋势,因为实际工作的算法的时间可能需要大量的数据,通过分析算法的运行时间和输入数据的规模的变化趋势就能大致的了解一个算法在其相应的环境中较好的工作

    ​ 上面的表示的方法并不简洁,在绝大多数情况下,我们设计的算法时间复杂度的多项式式子可能很长,这样仍旧不方便,那么我们**可以将一些常数,低阶项等运行次数对最高阶多项式影响不大的项删去,我们还可以将多项式的系数删去,**因为我们需要了解的是一个算法时间随数据的变化趋势,多项式的系数对时间的影响并不大,因此我们同样可以删去

    ​ 因此,上述代码的时间复杂度如下:
    T ( n ) = O ( n 2 ) T(n) = O(n^2) T(n)=O(n2)
    ​ 因此我们说这个算法的时间复杂度是n^2级别的

    ​ 上述就是大O复杂度分析

    4.多项式量级复杂度

    算法的复杂度根据量级可以分为多项式(Polynomial)和非多项式量级(Non-Deterministic Polynomial),举例O(2^n)和O(n!)属于非多项式量级的时间复杂度,即当数据规模n越来越大的时候,非多项式量级的算法执行时间将急剧增加,且增加速度很恐怖,所以非多项式量级的算法通常情况下是不可接受的低效的算法

    5.时间复杂度分析的简单规则

    当我们拿到一段代码,我们如何分析这段代码,如下是几个比较实用的方法:

    i. 只关注循环执行次数做多的一段代码

    ​ 刚才有讲过,对于大O复杂度分析只是一种变化趋势,我们通常会忽略掉公式中的常量,低阶项,系数等,我们只需要记录一个最大阶的量即可,因此我们在分析算法的复杂度的时候,只需要关注循环执行次数最多的一段代码即可。

    #include<map>
    #include<list>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<iomanip>
    #include<cstring>
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    #define R register
    #define LL long long
    #define pi 3.141
    #define INF 1400000000
    using namespace std;
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	int count = 0;
    	for (R int i = 0; i < n; ++i) {
    		++count;
    	}
    	return 0;
    }
    

    ​ 例如上述代码在定义变量和输入数据的时候时间复杂度是常量级别的时间复杂度,与数据规模无关,当数据规模变化的时候,时间复杂度基本没有影响,而主要影响因素在循环中,因此这段代码的总的时间复杂度就是O(n)

    ii. 加法法则:总复杂度等于量级最大的代码的时间复杂度

    #include<map>
    #include<list>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<iomanip>
    #include<cstring>
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    #define R register
    #define LL long long
    #define pi 3.141
    #define INF 1400000000
    using namespace std;
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	int count_1 = 0, count_2 = 0, count_3 = 0;
    	for (R int i = 0; i < n; ++i) {
    		++count_1;
    	}
    	for (R int i = 0; i < n; ++i) {
    		++count_2;
    	}
    	for (R int i = 0; i < n; ++i) {
    		for (R int j = 0; j < n; ++j) {
    			++count_3;
    		}
    	}
    	return 0;
    }
    

    ​ 对于上述代码,我们可以分析到这段代码的时间复杂度是:
    T ( n ) = O ( 5 ) + O ( n ) + O ( n ) + O ( n 2 ) T(n) = O(5) + O(n) + O(n) + O(n^2) T(n)=O(5)+O(n)+O(n)+O(n2)
    ​ 对于这样的时间复杂度,我们取其中最大的量级,所以这个算法总的时间复杂度是O(n^2)。因此**总的时间复杂度等于量级最大的代码的时间复杂度,我们可以将公式总结为:
    若 T 1 ( n ) = O ( f ( n ) ) , T 2 ( n ) = O ( g ( n ) ) 若 T1(n) = O(f(n)), T2(n) = O(g(n)) T1(n)=O(f(n)),T2(n)=O(g(n))

    则 T ( n ) = T 1 ( n ) + T 2 ( n ) = m a x ( O ( f ( n ) ) , O ( g ( n ) ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) 则 T(n) = T1(n) + T2(n) = max(O(f(n)), O(g(n))) = O(max(f(n), g(n))) T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))

    iii. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    #include<map>
    #include<list>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<iomanip>
    #include<cstring>
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    #define R register
    #define LL long long
    #define pi 3.141
    #define INF 1400000000
    using namespace std;
    
    inline int add(int n) {
    	int cnt = 0;
    	for (R int i = 0; i < n; ++i) {
    		cnt += i;
    	}
    	return cnt;
    }
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	int count = 0;
    	for (R int i = 0; i < n; ++i) {
    		count += add(i);
    	}
    	return 0;
    }
    

    ​ 对于上述代码,我们实现了代码的嵌套,循环每进行一次就调用一次函数,循环的时间复杂度是O(n)的,函数的时间复杂度是O(n)的,因此这段代码的时间复杂度是O(n^2)的

    ​ 因此乘法法则的公式我们可以总结为:
    T ( n ) = T 1 ( n ) × T 2 ( n ) = O ( n × n ) = O ( n 2 ) T(n) = T1(n) × T2(n) = O(n × n) = O(n^2) T(n)=T1(n)×T2(n)=O(n×n)=O(n2)

    6.两种时间复杂度

    ​ 对于对数级的时间复杂度,我们通常使用换底公式将对数换为以2为底的对数,因此我们通常忽略对数的底,统一将时间复杂度表示为O(logN)

    ​ 对于O(n + m) / O(n × m)量级的时间复杂度,我们无法事先评估大小,那么表述时间复杂度的时候需要全部写出

    7.常见的时间复杂度

    摘自维基百科->https://zh.wikipedia.org/zh-hans/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6

    非常常见已加粗表示

    名称运行时间(T(n))算法举例
    常数时间O(1)判断数字(二进制)奇偶性
    反阿克曼时间O(alpha (n))并查集单个操作的平摊时间
    迭代对数时间O(logn)分散式圆环着色问题
    对数对数时间O(loglogn)有界优先队列的单个操作
    对数时间O(logn)二分查找
    幂对数时间O(logN^2)
    幂时间O(n^c)(0 < c < 1)K-d树的搜索操作
    线性时间O(n)无序数组的搜索
    线性迭代对数时间O(nlogn)莱姆德·赛德尔的三角分割多边形算法
    线性对数时间O(nlogn)最快的比较排序
    二次时间O(n^2)冒泡排序,插入排序
    三次时间O(n^3)矩阵乘法的基本实现,计算部分相关性
    多项式时间线性规划中的卡马卡演算法,AKS质数测试
    准多项式时间
    次指数时间(第一定义)
    次指数时间(第二定义)
    指数时间2^O(n)使用动态规划解决旅行推销员问题
    阶乘时间O(n!)通过暴力搜索解决旅行推销员问题
    指数时间2^poly(n)
    双重指数时间22poly(n)在预膨胀算数中决定一个给定描述的真实性

    具体各时间复杂度详解参见维基百科

    8.空间复杂度分析

    内存复杂度的概念与时间复杂度类似,是计算一个程序使用的内存的增长趋势的方式

    与时间复杂度类似,渐进空间复杂度表示的是算法的存储空间随着数据规模变化的趋势,空间复杂度的分析较为容易

    例如下面的代码:

    #include<map>
    #include<list>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<iomanip>
    #include<cstring>
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    #define R register
    #define LL long long
    #define pi 3.141
    #define INF 1400000000
    using namespace std;
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	int count = 0;
    	int *number = new int[n];
    	for (R int i = 0; i < n; ++i) {
    		scanf("%d", &number[i]);
    	}
    	return 0;
    }
    

    上述代码申请了n个int大小的数组,并且数组大小随数据规模的变化而变化,此时的空间复杂度就是O(n)

    常用的空间复杂度有O(1),O(n),O(n^2)

    空间复杂度的分析比较简单,主要看是否有与数据规模相关的内存申请操作即可

    一般的算法竞赛会提供64MB/128MB/256MB的内存,一个int的大小是4B,假设给出128MB的空间,可以估算可以放得下的int的数组的大小为
    128 × 1 0 6 4 = 32 × 1 0 6 \frac{128 × 10^6}{4} = 32 × 10^6 4128×106=32×106
    所以说开百万级别的int数组是安全的(不过大的数组尽量不要开在子函数内,可能会爆栈),开千万级别的数组需要考虑,更不要开int flag[100000][100000](NOIP2012铺地毯出现过)

    9.不同情况下的复杂度分析

    除了上述各种情况下的复杂度分析外,我们还需要知道不同情况下的复杂度,主要的有如下的四种情况:最好,最坏;平均;均摊

    i. 最好最坏情况时间复杂度

    #include<map>
    #include<list>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<iomanip>
    #include<cstring>
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    #define R register
    #define LL long long
    #define pi 3.141
    #define INF 1400000000
    using namespace std;
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	int number[100];
    	int search;
    	scanf("%d", &search);
    	for (R int i = 0; i < n; ++i) {
    		scanf("%d", &number[i]);
    	}
    	for (R int i = 0; i < n; ++i) {
    		if (number[i] == search) {
    			printf("%d", i);
    			break;
    		}
    	}
    	return 0;
    }
    

    ​ 比如上面的例子,在数组种查找元素search并返回其位置,假如要查找的元素是数组的第一个元素,那么我们只需要执行一次就可以结束程序,那么这个算法的时间复杂度为O(1),即最好情况下的时间复杂度,假如我们需要查找的元素不在数组种,我们就需要执行n次才能结束算法,此时的时间复杂度即为O(n)此时对应的是最坏情况下的时间复杂度

    ii. 平均情况时间复杂度

    ​ 因为此时我们求的是平均情况,所以我们可以做个假设:这个数字在数组中的概率是1/2;不在数组中的概率是1/2;这个数字出现在0-1/n的概率是1/n,所以根据概率的乘法原理,要查找的数据出现在数组中的概率为1/2n,现在数组中的概率乘以任意位置的概率,然后我们就可以将每个元素被查找到时要查找的次数和对应的概率相乘,最后进行求和就可以得到算法的平均复杂度:
    1 × 1 2 n + 2 × 1 2 n + 3 × 1 2 n + . . . + n × 1 2 n + n × 1 2 = 3 n + 1 4 1 × \frac{1}{2n} + 2 × \frac{1}{2n} + 3 × \frac{1}{2n} + ... + n × \frac{1}{2n} + n × \frac{1}{2} = \frac{3n + 1}{4} 1×2n1+2×2n1+3×2n1+...+n×2n1+n×21=43n+1
    ​ 因为我们可以省略系数,所以上述的代码查找元素search的时间复杂度同样也是O(n),通常情况我们不需要严格分析这三种不同的情况。一般情况下,使用前面的复杂度分析方法计科,如果需要详细推导可以计算平均时间复杂度

    iii. 均摊时间复杂度

    ​ 均摊时间复杂度是一种特殊情况下的时间复杂度,并不是很常见,主要思想是把运行时间多的情况下的复杂度拆分,并均摊到运行时间少的情况下

    ​ 如下所示下面的代码:

    #include<map>
    #include<list>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<iomanip>
    #include<cstring>
    #include<iterator>
    #include<iostream>
    #include<algorithm>
    #define R register
    #define LL long long
    #define pi 3.141
    #define INF 1400000000
    using namespace std;
    
    int array_length;
    int number[100];
    
    inline void add(int value) {
    	if (array_length < 100) {
    		number[array_length] = value;
    		++array_length;
    	}
    	else {
    		int sum = 0;
    		for (R int i = 0; i < 100; ++i) {
    			sum += number[i];
    		}
    		number[0] = sum;
    	}
    }
    
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	for (R int i = 0; i < n; ++i) {
    		int num;
    		scanf("%d", &num);
    		add(num);
    	}
    	return 0;
    }
    

    ​ 上述代码实现了下述功能,向数组中从插入一个元素,当元素个数大于100后,将数组求和并将和放在数组第一个元素上;当元素少于100是,直接将元素插入空闲的位置上

    ​ 显然这两种情况的时间复杂度为O(n)和O(1),但是考虑到实际情况,实际情况下总是先将一个个位置存满后才执行求和操作,并且这两种情况的发生有规律

    ​ 我们可以将耗时的O(n)复杂度的代码均摊到不太耗时的O(1)上,这样总体的时间复杂度就会变成O(1),这就是均摊时间复杂度的均摊的思想,通常情况下均摊时间复杂运用在绝大多数情况下不太耗时,少数情况下耗时的操作,并且两种情况逻辑联系,有前后顺序

    10.算法时间复杂度与数据规模

    对比不同复杂度的增长,大概最大可以接收的数据如下表所示(具体情况具体分析)

    算法时间复杂度建议不超过的n的范围
    O(logn)很大,long long内均可
    O(n)10^7
    O(nlogn)10^5 - 5 * 10^5
    O(n^2)1000 - 5000
    O(n^3)200 - 500
    O(2^n)20 - 24
    O(n!)12

    11.总结

    我们在计算时间复杂度的时候,取代码中对时间增长贡献最大的一部分,从数学的角度来看就是取这个多项式的最大的一项

    分析时间的复杂度通常并不容易,对于只有很多for循环的程序,分析复杂度当然是容易的,但是当遇到递归的情况的时候,分析时间复杂度就相对麻烦

    另外时间复杂度是可以估算的,例如整个程序要从1到n进行二分,这边的时间复杂度是O(logn),每一次枚举需要进行一次k次验证的操作,算法的时间复杂度是O(k),那么整个程序的时间复杂度就是O(klogn)

    展开全文
  • 其他-时空复杂度分析

    2021-01-13 13:10:21
    1 时空复杂度分析 1.1 为什么要分析时空复杂度? 算法的时空复杂度越低,其效率就越高。算法复杂度是衡量程序优劣及效率的重要指标。 对于ACMer来说,我们面对的问题是完成可以在时空限制要求内对给定输出返回正确...

    为什么要分析时空复杂度?

    算法的时空复杂度越低,其效率就越高。算法复杂度是衡量程序优劣及效率的重要指标。

    对于ACMer来说,我们面对的问题是完成可以在时空限制要求内对给定输出返回正确输出的代码,所以我们必须要结合数据范围对算法进行时空复杂度分析。
    在这里插入图片描述

    时间复杂度(比较重要)

    时间频度

    一个算法执行所耗费的时间不仅仅与代码有关,必须上机运行测试才能知道。但我们可以对代码运行的时间进行粗略分析。

    一个算法花费的时间与算法中语句的执行次数成正相关。一般来说,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度,记为T(n)。(n为输入数据的规模,例如输入含有n个元素的数组a[],让我们将a[]数组排序。)

    时间复杂度

    引入时间复杂度概念。在写完代码时候再逐条统计语句的运行次数太过麻烦而没有必要。

    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。时间复杂度是问题规模趋于无穷时算法运行时间优劣的比较依据。

    一般来说取T(n)最高次项,并舍掉其系数即可作为其时间复杂度。常见的时间复杂度有:O(1) < O(logn) < O(n) < O(nlogn) < O ( n 2 ) O(n^{2}) O(n2) < O ( n 3 ) O(n^3) O(n3 < O ( 2 n ) O(2^n) O(2n) < O(n!)等。

    ACM中的时间复杂度

    我们无需对每道题的时间复杂度严格证明,只需粗略分析代码是否会超时。
    在竞赛中,一般认为计算机一秒能执行 5 ∗ 1 0 8 5*10^8 5108 次计算,如果题目给出的时间限制为1秒,那么选择的算法执行的计算次数最多应该在 1 0 8 10^8 108量级才有可能解决这个题目。
    一般情况下:
    在这里插入图片描述

    以上范围仅供参考,实际过程中还要考虑每种算法的常数。

    空间复杂度(不怎么重要)

    空间复杂度

    空间复杂度类似于时间复杂度的讨论,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。
    算法的输入输出数据所占用的存储空间是由要解决的问题决定的,所以
    存储算法本身所占用的存储空间在完成代码之后为一个常量,并不重要,在竞赛中若存在代码长度限制一般会另行规定。
    算法在运行过程中临时占用的存储空间随算法的不同而异,并不会超过时间复杂度。
    可以发现空间复杂度一定不会超过时间复杂度。综上,所以没有什么人分析空间复杂度。

    ACM中的空间限制

    通过定义变量所占字节数的累加我们可以求得代码所使用的空间。但空间卡得很死的题一般被称作毒瘤题,所以以下内容但当涉猎。
    了解空间的计算之前,我们先来了解一下计算机储存的单位B(Byte)。
    1KB=1024B
    1MB=1024KB
    1Gb=1024MB
    知道这些后,我们来了解各种类型所占的B(字节)数,就可以进行空间复杂度计算了。

    数据类型\编译平台16位32位64位
    char111
    int244
    long long448
    float444
    double888
    short222
    指针248
    展开全文
  • 各种排序时空复杂度比较图
  • Java时空复杂度

    2020-08-03 21:18:33
    Java时空复杂度算法效率时间复杂度空间复杂度 算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被 称作空间复杂度。 时间复杂度主要衡量的是一个算法的...
  • 时空复杂度简述

    2021-04-07 20:48:38
    时空复杂度简述 时间复杂度 计算机的运行能力估计: 做一个简单实验,让程序循环1亿次,10亿次看看需要多少时间。 可以看出,一般电脑在1亿次可在1秒内完成,超过10亿次在1秒内难以完成。 时间复杂度估算方法 简单...
  • 各种常用排序算法时空复杂度汇总 如图
  • dfs的时空复杂度分析

    2020-08-18 17:38:00
    以下仅考虑dfs所使用的时空复杂度,不考虑其他 时间复杂度 = 递归树每层的节点个数 * 递归树的深度 空间复杂度 = 递归树的深度
  • 各内排序算法时空复杂度对比表 ...
  • 这些都是算法时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。  O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。 O(1)解析 O(1)...
  • 矩阵 减小时空复杂度

    2015-09-02 13:00:16
    矩阵 问题 怎么减小时空复杂度![图片](https://img-ask.csdn.net/upload/201509/02/1441198772_736021.png)
  • 第3课 算法的时空复杂度_2019-11-12
  • 算法的时空复杂度的比较 1. 算法的时间复杂度 在不耗费过多资源的前提下,或者说在相同资源的前提下,通过调整代码的执行逻辑,来降低程序的时间复杂度即程序的执行时间,可以极大地提升程序的执行效率。 主要的算法...
  • 时空复杂度之质数问题 题目 有m组数据,每组数据有n个小于1000的正整数,分别求每组数据中所有素数的和。其中1<=m<=10;1<=n<=1000; 方法一: #include<stdio.h> #include <stdlib.h> int ...
  • 各种排序算法时空复杂度分析

    千次阅读 2016-09-08 20:34:04
    各种排序算法时空复杂度分析表
  • 为了实现在视频发送端或中间传输节点实时评估用户感知质量和在中间节点通过视频传输质量来监控网络质量,提出一种基于时空复杂度的实时视频满意度评估模型。利用I帧中4×4块所占比例和亮度信息代表视频空间复杂度,...
  • 算法: 时间复杂度: 原文地址:... 时空复杂度: https://www.cnblogs.com/zakers/archive/2015/09/14/4808821.html 推荐:http://blog.csdn.net/yangwei282367751/articl...
  • 机器学习的时空复杂度 机器学习 (Machine Learning) The train time complexity of machine learning model — The amount of time taken to train the model 机器学习模型的训练时间复杂度 -训练模型花费的时间 The...
  • 时空复杂度之珠心算测验 问题 珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练, 既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。 某学校的珠心算老师采用一...
  • 数据结构1-时空复杂度 程序设计=算法+数据结构。  算法:解决特点问题的求解步骤的描述,表现为计算机中的有限条指令。  算法具有确定性、可行性、有穷性三个特性。 时间复杂度 简言之,时间复杂度就...
  • 个人认为一段代码的好坏可以从良好的代码习惯和算法上来看。...而算法的优劣可以用时空复杂度来进行评估。 时间复杂度: 时间复杂度是算法的时间效率也就是说是代码运行所耗费的时间。代码运行所耗费的时...
  • 自学算法之时空复杂度的计算

    千次阅读 2018-03-21 10:59:18
    直接进入时空复杂度的计算。首先。时间复杂度概念:算法需要运行的时间,一般将算法的执行次数作为时间复杂度的度量标准。我们看算法1:  int sum = 0; //运行1次  int total = 0; //运行1次  for(int i = 0; ...
  • 2.时空复杂度 3.稳定性 4.使用情况分析 排序算法总结(C语言版)已介绍排序算法的基本思想和C语言实现,本文只介绍时空复杂度和稳定性。 1.基本概念 时间复杂度: 一个算法花费的时间与算法中语句的执行次数成正...
  • Acwing《算法基础课》第7章 时空复杂度分析 文章目录Acwing《算法基础课》第7章 时空复杂度分析 一般ACM或者笔试题的时间限制是111秒或222秒 C++一般111s能计算10710^7107~10810^8108次,在这种情况下,C++代码中的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,312
精华内容 4,924
关键字:

时空复杂度