0

我是 CompSci 1 的 10 年级学生。在我们的教科书Practical Programming 3rd Edition, An Introduction to Computer Science Using Python 3.6中，它提到了荷兰国旗问题。以下是它如何逐字说明练习：

Edsgar Dijkstra 以其在编程语言方面的工作而闻名。他提出了一个巧妙的问题，他称之为荷兰国旗问题：给定一个字符串列表，每个字符串要么是“red”、“green”或“blue”（每个在列表中表示多次），重新排列列表，使字符串按照荷兰国旗的顺序排列——首先是所有“红色”字符串，然后是所有“绿色”字符串，然后是所有“蓝色”字符串。

这是我为练习编写的 python 代码：

def dutch_flag(colors: list)-> list:
  """
  This function takes a list of strings of colors (red, green, 
  or blue),and returns a list containing them with the reds first, 
  the greens second, and the blues last.
  """
  reds = 0
  greens = 0
  blues = 0
  for color in colors:
    color = color.lower().strip()
    if color == "red":
      reds += 1
    elif color == "green":
      greens += 1
    elif color == "blue":
      blues += 1

  flag = []
  for i in range(0, reds):
    flag.append("red")
  for i in range(0, greens):
    flag.append("green")
  for i in range(0, blues):
    flag.append("blue")

  return flag

我的代码在 O(n) 时间内运行。但是，我的老师告诉我们，这个程序需要一个排序算法，充其量是 O(n*logn)。为什么我的代码更快？

4

1 回答 1

1

你展示的是计数排序。其他非比较选项是桶排序或基数排序，它们也具有 O(n) 时间复杂度。

也可以使用基于比较的 3 路分区函数来解决这个问题，该函数使用时间复杂度 O(n) 的比较和交换。

https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Pseudocode

通常基于比较的排序需要 O(n log(n)) 时间，但荷兰国旗问题不需要这个。

可以扩展 3 路分区功能以处理更多颜色。第一遍将数组分成 3 个子数组，小、中、大，然后对每个子数组重复该过程，将其分成 3 个子子数组，依此类推。9种颜色可以在2遍中完成，第1遍分为小，中，大，然后第2遍将每个子阵列分成3部分，这也是O（n）时间复杂度。对于n个元素和k种颜色，时间复杂度是O(n⌈log3(k)⌉)，但是由于k是常数，所以时间复杂度是O(n)。

于 2019-04-05T20:20:44.587 回答