算法的时间和空间代价

算法的时间和空间代价
对抽象算法,通常无法做精确度量,只能退而求其次,设法估计算法复杂性的量级

例:求两个 n×n 矩阵乘积的常规乘法算法

主要运算:乘法(或加法)

空间单位:一个元素所占存储 s;时间单位:一次乘法所用时间 t

实例规模:矩阵一行(一列)的元素个数

时间复杂性:f(n) ≈ n×n×n = n3(单位为 t)

空间复杂性:只考虑完成算法所需空间,包括结果的存储空间和计算中临时使用的辅助空间,这里约为 n2 (结果矩阵所需空间

参考
https://blog.csdn.net/u012861467/article/details/79913307

原文地址:https://www.cnblogs.com/wangjiale1024/p/10270552.html