O(n) 中的荷兰国旗问题 运行
Dutch National Flag Problem Running in O(n)
我是 CompSci 1 的 10 年级学生。在我们的教科书 Practical Programming 3rd Edition, An Introduction to Computer Science Using Python 3.6 中，它提到了荷兰国旗问题。以下是它逐字逐句地陈述练习的方式：
Edsgar Dijkstra is known for his work on programming languages. He came up with a neat problem that he called the Dutch National Flag problem: given a list of strings, each of which is either "red", "green", or "blue" (each is represented several times in the list), rearrange the list so that the strings are in the order of the Dutch national flag--all the "red" strings first, then all the "green" strings, then all the "blue" strings.
这是我为练习编写的 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)。为什么我的代码更快？
你显示的是计数排序。其他非比较选项是桶排序或基数排序，它们也具有 O(n) 时间复杂度。
也可以通过使用时间复杂度为 O(n) 的比较和交换的基于比较的 3 向分区函数来解决此问题。
https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Pseudocode
通常基于比较的排序需要 O(n log(n)) 时间，但荷兰国旗问题不需要这个。
可以扩展 3 路分区功能以处理更多的颜色。第一遍将数组分成 3 个子数组，small、middle、large，然后在每个子数组上重复该过程，将其拆分为 3 个 sub-sub 数组，依此类推。 9 种颜色可以在 2 遍中完成，第 1 遍分为小、中、大，然后第 2 遍将每个子数组分成 3 个部分，这也是 O(n) 时间复杂度。对于n个元素和k种颜色，时间复杂度为O(n⌈log3(k)⌉)，但由于k是常数，所以时间复杂度为O(n)。
我是 CompSci 1 的 10 年级学生。在我们的教科书 Practical Programming 3rd Edition, An Introduction to Computer Science Using Python 3.6 中，它提到了荷兰国旗问题。以下是它逐字逐句地陈述练习的方式：
Edsgar Dijkstra is known for his work on programming languages. He came up with a neat problem that he called the Dutch National Flag problem: given a list of strings, each of which is either "red", "green", or "blue" (each is represented several times in the list), rearrange the list so that the strings are in the order of the Dutch national flag--all the "red" strings first, then all the "green" strings, then all the "blue" strings.
这是我为练习编写的 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)。为什么我的代码更快？
你显示的是计数排序。其他非比较选项是桶排序或基数排序，它们也具有 O(n) 时间复杂度。
也可以通过使用时间复杂度为 O(n) 的比较和交换的基于比较的 3 向分区函数来解决此问题。
https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Pseudocode
通常基于比较的排序需要 O(n log(n)) 时间，但荷兰国旗问题不需要这个。
可以扩展 3 路分区功能以处理更多的颜色。第一遍将数组分成 3 个子数组，small、middle、large，然后在每个子数组上重复该过程，将其拆分为 3 个 sub-sub 数组，依此类推。 9 种颜色可以在 2 遍中完成，第 1 遍分为小、中、大，然后第 2 遍将每个子数组分成 3 个部分，这也是 O(n) 时间复杂度。对于n个元素和k种颜色，时间复杂度为O(n⌈log3(k)⌉)，但由于k是常数，所以时间复杂度为O(n)。