代码随想录01:算法性能分析

BBigSun 评论157阅读模式

代码随想录01:算法性能分析

时间复杂度分析

O(n)文章源自十年又十年-https://www.bbigsun.com/394.html

  • 时间换空间

空间复杂度分析

S(n)文章源自十年又十年-https://www.bbigsun.com/394.html

  • 空间换时间

递归算法的时间复杂度

递归算法的时间复杂度取决于:递归的次数 * 每次递归中的操作次数。文章源自十年又十年-https://www.bbigsun.com/394.html

题目:求 x 的 n 次方?文章源自十年又十年-https://www.bbigsun.com/394.html

方法一:文章源自十年又十年-https://www.bbigsun.com/394.html

  • 时间复杂度 O(n)
def function1(x, n):
    result = 1
    for i in range(n):
        result *= x
    return result

方法二:文章源自十年又十年-https://www.bbigsun.com/394.html

  • 时间复杂度 O(n)

x^5 = 1*x*x*x*x*x 计算5次文章源自十年又十年-https://www.bbigsun.com/394.html

def function2(x, n):
    if n == 0:
        return 1
    else:
        return function2(x, n-1) * x

方法三:文章源自十年又十年-https://www.bbigsun.com/394.html

  • 时间复杂度:O(logn)

x^4 = x^2 * x^2 = x*x * x*x 计算2次
x^5 = x^2 * x^2 * x 计算2次文章源自十年又十年-https://www.bbigsun.com/394.html

def function3(x, n):
    if n == 0: return 1
    if n == 1: return x
    # 空间换时间,不管n为奇数还是偶数,t值一样
    t = function3(x, n/2)
    # 如果n为奇数,多乘以个x返回
    if n%2 == 1: return t*t*x
    # 如果n为偶数,直接返回t值
    return t * t
文章源自十年又十年-https://www.bbigsun.com/394.html

纸上得来终觉浅,绝知此事要躬行。

weinxin
17688689121
我的微信
微信扫一扫
BBigSun
  • 本文由 BBigSun 发表于 2023年 3月 29日 16:50:56
  • 转载请务必保留本文链接:https://www.bbigsun.com/394.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定