本文共 2044 字，大约阅读时间需要 6 分钟。

主要材料来源

时间复杂度

• 概念
  • 执行当前算法所消耗的时间(最坏情况的运行时间)
• 推导O阶的方法
  • 用常数1取代运行时间中的所有加法常数
  • 在修改后的运行次数函数中，只保留最高阶项。
  • 如果最高阶项存在且不是1，则去掉该最高阶项系数。
  • 得到的最后结果就是O阶
• 常用的时间复杂度所耗费的时间从小到大依次是
  $O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$
• 常见复杂度量级
  • 常数阶O(1)：没有循环等复杂结构
  • 线性阶O(n)：循环$n$次

    i = 0while i <= n:  i += 1

  • 对数阶O(log(n))

    i = 1while i <= n:   i *= m

    $m$为常数，则循环次数$x$：$m^x=n\Rightarrow x=lo{g}_{m}n$，故量级为：$log(n)$
  • 线性对数阶O(nlog(n))：将复杂度为对数阶O(log(n))的代码循环$n$次，则其复杂度为：$n\times log(n)$，即：O(nlog(n))
  • 平方阶O(n²)：复杂度为O(n)的代码嵌套循环
  • 立方阶O(n³)、$k$次方阶O(n^k)：同O(n²)
• 常见排序算法复杂度

空间复杂度

• 概念
  • 执行当前算法需要占用的内存空间
• 常见复杂度量级
  • O(1)：算法执行所需要的临时空间不随着某个变量$n$的大小而变化
    • 场景
      • 变量赋值（变量分配的内存不会随着处理数据量的变化而变化）
      • 变量数学计算（同上）

      x = 91y = 100while y > 0:   if x > 100:      x -= 10      y -= 1   else:     x += 1
  • O(n)：数组，列表等，随着元素的增多，内存将会增加

两者都平衡

• 判断是否闰年
  • 空间复杂度 > 时间复杂度：算法判断
  • 时间复杂度 > 空间复杂度：列表

转载地址：https://blog.csdn.net/fish2009122/article/details/106566043 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！