算法复杂度(Algorithm Complexity)


Recall

  • 按照纬度划分为时间复杂度和空间复杂度
  • 是一种描述随着调用的次数增加而消耗增加趋势的一种函数
  • 只是描述一个规律而不是精确的时间
  • 常见的复杂度的函数有:
    • 常数阶O(1)
    • 对数阶O(logN)
    • 线性阶O(n)
    • 线性对数阶O(nlogN)
    • 平方阶O(n²)
    • 立方阶O(n³)
    • K次方阶O(n^k)
    • 指数阶(2^n)
  • 时间复杂度用T(n)表示,空间复杂度用T(n)来表示,他们对应的表达式都是O(n)这些复杂度函数。常用的用例是worst-case time complexity,不常用的有:average-case complexity

Notes

  • 算法复杂度分为时间复杂度和空间复杂度。

    1时间复杂度指的是执行算法所需要的计算工作量。它指的不是一个具体的时间,而是算法随着条件不同的一个变化趋势。

    维基百科中定义的是:时间复杂度指的是计算的复杂度,用来描述执行某个算法所用的时间,它用来描述算法的基本运算执行了任意次后的时间,因为算法实际每次执行的时间不尽相同,但是我们假设每次执行的时间都是恒定的,并且一般来说会取使用时间最大(worst-case time complexity,对应的是average-case complexity,后面这种用例不是很常用)的一次来作为恒定因子(a constant factor)。因为这种复杂度是描述当输入次数增加时的时间变化的函数,所以一般使用大写O来表示,O(f(x)),常见的f(x)函数如下:

    • 常数阶O(1)
    • 对数阶O(logN)
    • 线性阶O(n)
    • 线性对数阶O(nlogN)
    • 平方阶O(n²)
    • 立方阶O(n³)
    • K次方阶O(n^k)
    • 指数阶(2^n)

    上面从上至下依次的时间复杂度越来越大,执行的效率越来越低。

    T(n) = O( f(n) ),T指的是复杂度,一般我们使用的是最耗时时间复杂度用例。

    2⃣️空间复杂度是指执行这个算法所需要的内存空间。同样它也不是值算法执行所需的具体内存,而是指内存使用的一个趋势。

SUMMARY:时间复杂度和空间复杂度用来描述算法损耗的规律,两者各有优势,在实际使用中需要根据实际场景来选择合适的方案。

相关连接:

算法的时间与空间复杂度(一看就懂) - 知乎

时间复杂度 - 维基百科,自由的百科全书

Time complexity - Wikipedia

声明:Eironn's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 算法复杂度(Algorithm Complexity)


Java开发,同时会一些旁门左道。