Section 195.1: 双端队列操作

双端队列是一种两端都可以添加和删除元素的队列。

class Deque:
  def __init__(self):
    self.items = []

  def isEmpty(self):
    return self.items == []

  def addFront(self, item):
    self.items.append(item)

  def addRear(self, item):
    self.items.insert(0,item)

  def removeFront(self):
    return self.items.pop()

  def removeRear(self):
    return self.items.pop(0)

 def size(self):
  return len(self.items)

操作：平均情况（假设参数是随机生成的）

Append : O(1)
Appendleft : O(1)
Copy : O(n)
Extend : O(k)
Extendleft : O(k)
Pop : O(1)
Popleft : O(1)
Remove : O(n)
Rotate : O(k)

Section 195.2: 算法符号

在任何计算机语言中，优化都有一些通用原则，Python 也不例外。不要边写边优化：不要考虑可能的优化，而是专注于确保代码清晰、正确且易于理解。如果完成时代码太大或太慢，那么您可以考虑对其进行优化。

记住 80/20 原则：在许多领域，您可以花费 20% 的努力获得 80% 的结果（也称为 90/10 原则——这取决于您与谁交谈）。每当您准备优化代码时，请使用性能分析来找出那 80% 的执行时间去了哪里，这样您就会知道在哪里集中精力。

始终运行“之前”和“之后”的基准测试：否则您怎么知道您的优化实际上是否有所改善？如果您的优化后的代码仅比原始版本稍快或稍小，请撤销更改并返回到原始的清晰代码。

使用正确的算法和数据结构：不要使用 O(n²) 的冒泡排序算法来对一千个元素进行排序，而当有 O(n log n) 的快速排序可用时。同样，不要将一千个项目存储在需要 O(n) 搜索的数组中，而您可以使用 O(log n) 的二叉树或 O(1) 的 Python 哈希表。

更多内容，请访问以下链接……Python 加速

以下是用于表示算法时间复杂度的三种渐进符号。

  1. Θ 符号：Theta 符号从上下界限制一个函数，因此它定义了确切的渐进行为。简化 Theta 符号表达式的方法是去掉低阶项并忽略首项常数。例如，考虑以下表达式。3n³ + 6n² + 6000 = Θ(n³) 去掉低阶项总是可行的，因为总会有一个 n₀，使得当 n ≥ n₀ 时，Θ(n³) 的值总是高于 Θ(n²)，无论涉及的常数如何。对于给定的函数 g(n)，我们用 Θ(g(n)) 表示以下函数集合。Θ(g(n)) = {f(n): 存在正常数 c₁、c₂ 和 n₀，使得对于所有 n ≥ n₀，有 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n)} 上述定义意味着，如果 f(n) 是 g(n) 的 Theta，那么对于较大的 n（n ≥ n₀），f(n) 的值总是介于 c₁g(n) 和 c₂g(n) 之间。Theta 的定义还要求，对于大于 n₀ 的 n，f(n) 必须是非负的。
  2. 大 O 符号：大 O 符号定义了算法的上界，它仅从上方限制一个函数。例如，考虑插入排序的情况。在最好情况下，它需要线性时间，在最坏情况下，它需要二次时间。我们可以安全地说，插入排序的时间复杂度是 O(n²)。注意，O(n²) 也涵盖了线性时间。如果我们使用 Theta 符号来表示插入排序的时间复杂度，我们需要分别用两条语句来表示最好和最坏情况：
    1. 插入排序的最坏情况时间复杂度是 Θ(n²)。
    2. 插入排序的最好情况时间复杂度是 Θ(n)。

大 O 符号在我们只知道算法的时间复杂度上界时非常有用。很多时候，我们可以通过简单地查看算法轻松找到上界。O(g(n)) = {f(n): 存在正常数 c 和 n₀，使得对于所有 n ≥ n₀，有 0 ≤ f(n) ≤ cg(n)}

  1. Ω 符号：正如大 O 符号提供了函数的渐进上界一样，Ω 符号提供了渐进下界。Ω 符号在我们有算法的时间复杂度下界时可以很有用。正如前一篇文章中讨论的那样，算法的最佳性能通常并不有用，因此 Omega 符号是三种符号中最少使用的。对于给定的函数 g(n)，我们用 Ω(g(n)) 表示以下函数集合。Ω(g(n)) = {f(n): 存在正常数 c 和 n₀，使得对于所有 n ≥ n₀，有 0 ≤ cg(n) ≤ f(n)}。让我们仍然以插入排序为例。插入排序的时间复杂度可以写成 Ω(n)，但这并不是关于插入排序的很有用的信息，因为我们通常对最坏情况和有时的平均情况感兴趣。

Section 195.3: 符号

基本思想

描述 Python 程序速度时使用的符号称为大 O 符号。假设您有一个函数：

def list_check(to_check, the_list):
  for item in the_list:
    if to_check == item:
      return True
  return False

这是一个简单的函数，用于检查一个项目是否在列表中。要描述这个函数的复杂性，您会说 O(n)。这意味着“n 的阶”，因为 O 函数被称为阶函数。

O(n) - 通常 n 是容器中项目的数量
O(k) - 通常 k 是参数的值或参数中元素的数量

Section 195.4: 列表操作

操作：平均情况（假设参数是随机生成的）：最坏情况

Append : O(1)
Copy : O(n)
Del slice : O(n)
Delete item : O(n)
Insert : O(n)
Get item : O(1)
Set item : O(1)
Iteration : O(n)
Get slice : O(k)
Set slice : O(n + k)
Extend : O(k)
Sort : O(n log n)
Multiply : O(nk)
x in s : O(n)
min(s), max(s) :O(n)
Get length : O(1)

Section 195.5: 集合操作

操作：平均情况（假设参数是随机生成的）：最坏情况

x in s : O(1)
Difference s - t : O(len(s))
Intersection s&t : O(min(len(s), len(t))) : O(len(s) * len(t)
Multiple intersection s1&s2&s3&...&sn : : (n-1) * O(l) where l is max(len(s1),...,len(sn))
s.difference_update(t) : O(len(t)) : O(len(t) * len(s))
s.symetric_difference_update(t) : O(len(t))
Symetric difference s^t : O(len(s)) : O(len(s) * len(t))
Union s|t : O(len(s) + len(t))