文章 32
评论 275
浏览 46885
算法的时间复杂度计算

算法的时间复杂度计算

写在前面

   时间复杂度与空间复杂度直接决定着一个算法的好坏,而大多时候在设计算法是时间复杂度要优先于空间复杂度。

时间复杂度是什么(以下内容来着维基百科)

计算机科学中,算法时间复杂度(Time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

为了计算时间复杂度,我们通常会估计算法的操作单元数量,每个单元运行的时间都是相同的。因此,总运行时间和算法的操作单元数量最多相差一个常量系数。

相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度,记为 T(n) ,定义为任何大小的输入 n 所需的最大运行时间。另一种较少使用的方法是平均情况复杂度,通常有特别指定才会使用。时间复杂度可以用函数 T(n) 的自然特性加以分类,举例来说,有着 T(n) = O(n) 的算法被称作“线性时间算法”;而 T(n) = O(M**n) 和 M**n= O(T(n)) ,其中 Mn > 1 的算法被称作“指数时间算法”。

常见算法时间复杂度

搜索

image.png

排序

image.png

数据结构

image.png

image.png

image.png

计算时间复杂度

算法的时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n))。它表示随着 输入大小 n 的增大,算法执行需要的时间的增长速度可以用 f(n) 来描述
1.在一个函数中,常数项对于函数的增长速度并不大,随意当 T(n)= 一个常数事,我们就可以说这个算法的时间复杂度为 O(1);

func main() {
   i := 1
   fmt.Println(i)
}
// 该函数总共两条执行语句,所以时间复杂度T(n) = 2,所以时间复杂度为O(1)

2.如果 T(n)不等于一个常数项时,可直接将常数项省略

for i := 0; i < n; i++ {
	sum += i
}
sum += 1
sum += 2
sum += 3
此函数共执行了 n+3次,所以T(n) = n+3,时间复杂度为O(n)

3.对于有高次幂的,低次幂的影响可以说是微乎其微。比如 n^3 对于 n^2,n^2 对于 n,由于时间复杂度要求不是特别高,所以低次幂直接忽略

    for i := 0; i < n; i++ {

        for j := 0; j < n; j++ {

            for k := 0; k < n; k++ {
                // xxx
            }
        }
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
                // xxx
        }
    }
上面函数的执行次数为n^3 + n^2,所以T(n) = n^3 + n^2, 时间复杂度为O(n^3) 

4.因为函数的阶数对函数的增长速度的影响是最显著的,所以我们忽略与最高阶相乘的常数。

比如
T(n) = 3n^3,此时时间复杂度为 O(n^3)。

综合一下:只取最高次幂,最高次幂常数归 1


文章发布自:墨殇的技术博客,转载请注明出处,谢谢!

凡打不倒我的,必使我强大!!!—— 墨殇的技术博客