在最坏的情况下，在 cribbage O(N*log(N)) 中计算运行的计算复杂度是多少？
Is the computational complexity of counting runs in cribbage O(N*log(N)) in the worst case?
在纸牌游戏 cribbage 中，计算手牌的 运行s 在表演期间（游戏回合的一个阶段）报告最长的递增子序列，它仅包含递增的值乘以 1。如果此子序列中存在重复值，则报告双 运行（或三重、四重等）。
一些示例：
("A","2","3","4","5") => (1,5) 单 运行 5
("A","2","3","4","4") => (2,4) Double 运行 for 4
("A","2","3","3","3") => (3,3) 三重 运行 为 3
("A","2","3","4","6") => (1,4) 单 运行 for 4
("A","2","3","5","6") => (1,3) 单 运行 为 3
("A","2","4","5","7") => (0,0) 否 运行s
为了解决手大于 5 手大小的情况。如果 运行 具有子序列重复数与子序列长度的最大乘积，将被选中。
一些相关的例子：
("A","2","2","3","5","6","7","8","9","T","J") => (1,7) 单 运行 为 7
("A","2","2","3","5","6","7","8") => (2,3) Double 运行 for 3
我找到最高分运行的方法如下：
- 创建排名列表并对其进行排序。 O(N*log(N))
- 创建一个列表来存储最大 运行 长度的长度以及存在多少重复项。将其初始化为 [1 个副本，1 个长]。
- 创建一个与上面相同的列表来存储当前 运行。
- 创建一个标志，指示您遇到的重复项是否不是该值的初始副本。将其初始化为 False。
- 如果在初始重复后发现额外的重复值，则创建一个变量来存储重复子序列的增加。初始化为 1.
- 遍历相邻元素之间的差异。 O(N)
- 如果差值大于一，则运行结束。检查 max 运行 的元素的乘积是否小于当前 运行 和当前 运行 的长度是否为 3 或更大。如果为真，则当前 运行 变为最大值 运行 并且当前 运行 列表重置为 [1,1]。该标志重置为 False。重复子序列的增量重置为 1。迭代到下一个值。
- 如果差值为 1，则将当前 运行 的长度增加 1，并将标志设置为 False。迭代到下一个值。
- 如果差异为 0 且标志为 False，则将重复子序列的增量设置为等于 运行 的当前重复数。然后，将 运行 的重复数加倍并将标志设置为 True。迭代到下一个值
- 如果差异为 0 且标志为 True，则将 运行 的数量增加重复子序列值的增量。
- 迭代后，检查当前 运行 列表，如第 7 步中所示，对照最大值 运行 并相应地设置最大值 运行。
我相信这有 O(N*(1+log(N))。我相信这是最好的时间复杂度，但我不确定如何证明这一点或更好的算法会是什么样子。是有没有一种方法可以在不先对列表进行排序的情况下实现更好的时间复杂度？如果没有，如何证明这是最佳时间复杂度？
迭代
之间的差异
算法的时间复杂度是well-traveled路径。 证明算法的复杂度在数学家集群之间略有不同；相反，复杂性社区通常使用模块化 pseudo-code 和标准缩减。例如，基于输入长度的 for 循环是 O(N)（惊喜）；已知对列表进行排序最多为 O(log N)（在一般情况下）。好的治疗，见Big O, how do you calculate/approximate it?.
注意：O(N x (1+log(N)) 是一种略微草率的表示法。只有最大的复杂性因子——占主导地位的 N 接近无穷大——被使用。删除 1+：它只是 O(N log N).
正如我在评论中所建议的那样，您可以简单地对元素进行计数。保留一张计数列表，以您的卡值作为索引。为了讨论算法，不要使用字符表示的“脏”数据：“A23456789TJQK”；只需使用它们的值，0-12 或 1-13。
for rank in hand:
count[rank] += 1
这是对数据的线性传递，O(N)。
现在，遍历计数数组，找到最长的 non-zero 值序列。这是一个包含 13 个元素的 fixed-length 列表，每个元素只接触一次：O(1)。如果你积累了一个倍数列表（卡计数，那么你最后也会有你的组合因子。
因此，生成的算法和代码是 O(N)。
例如，让我们将其缩短为 7 个牌值，0-6。给定输入整数
1 2 1 3 6 1 3 5 0
您完成了第一次计数项目：
[1 3 1 2 0 1 1]
第二次传递给你最大 运行 长度为 4，计数为 [1 3 1 2]。
您报告的 运行 为 4、三重和双倍，或者点数
4 * (1 * 3 * 1 * 2)
您还可以计算对值：
2 * 3! + 2 * 2!
在纸牌游戏 cribbage 中，计算手牌的 运行s 在表演期间（游戏回合的一个阶段）报告最长的递增子序列，它仅包含递增的值乘以 1。如果此子序列中存在重复值，则报告双 运行（或三重、四重等）。
一些示例：
("A","2","3","4","5") => (1,5) 单 运行 5
("A","2","3","4","4") => (2,4) Double 运行 for 4
("A","2","3","3","3") => (3,3) 三重 运行 为 3
("A","2","3","4","6") => (1,4) 单 运行 for 4
("A","2","3","5","6") => (1,3) 单 运行 为 3
("A","2","4","5","7") => (0,0) 否 运行s
为了解决手大于 5 手大小的情况。如果 运行 具有子序列重复数与子序列长度的最大乘积，将被选中。
一些相关的例子：
("A","2","2","3","5","6","7","8","9","T","J") => (1,7) 单 运行 为 7 ("A","2","2","3","5","6","7","8") => (2,3) Double 运行 for 3
我找到最高分运行的方法如下：
- 创建排名列表并对其进行排序。 O(N*log(N))
- 创建一个列表来存储最大 运行 长度的长度以及存在多少重复项。将其初始化为 [1 个副本，1 个长]。
- 创建一个与上面相同的列表来存储当前 运行。
- 创建一个标志，指示您遇到的重复项是否不是该值的初始副本。将其初始化为 False。
- 如果在初始重复后发现额外的重复值，则创建一个变量来存储重复子序列的增加。初始化为 1.
- 遍历相邻元素之间的差异。 O(N)
- 如果差值大于一，则运行结束。检查 max 运行 的元素的乘积是否小于当前 运行 和当前 运行 的长度是否为 3 或更大。如果为真，则当前 运行 变为最大值 运行 并且当前 运行 列表重置为 [1,1]。该标志重置为 False。重复子序列的增量重置为 1。迭代到下一个值。
- 如果差值为 1，则将当前 运行 的长度增加 1，并将标志设置为 False。迭代到下一个值。
- 如果差异为 0 且标志为 False，则将重复子序列的增量设置为等于 运行 的当前重复数。然后，将 运行 的重复数加倍并将标志设置为 True。迭代到下一个值
- 如果差异为 0 且标志为 True，则将 运行 的数量增加重复子序列值的增量。
- 迭代后，检查当前 运行 列表，如第 7 步中所示，对照最大值 运行 并相应地设置最大值 运行。
我相信这有 O(N*(1+log(N))。我相信这是最好的时间复杂度，但我不确定如何证明这一点或更好的算法会是什么样子。是有没有一种方法可以在不先对列表进行排序的情况下实现更好的时间复杂度？如果没有，如何证明这是最佳时间复杂度？
迭代
之间的差异算法的时间复杂度是well-traveled路径。 证明算法的复杂度在数学家集群之间略有不同；相反，复杂性社区通常使用模块化 pseudo-code 和标准缩减。例如，基于输入长度的 for 循环是 O(N)（惊喜）；已知对列表进行排序最多为 O(log N)（在一般情况下）。好的治疗，见Big O, how do you calculate/approximate it?.
注意：O(N x (1+log(N)) 是一种略微草率的表示法。只有最大的复杂性因子——占主导地位的 N 接近无穷大——被使用。删除 1+：它只是 O(N log N).
正如我在评论中所建议的那样，您可以简单地对元素进行计数。保留一张计数列表，以您的卡值作为索引。为了讨论算法，不要使用字符表示的“脏”数据：“A23456789TJQK”；只需使用它们的值，0-12 或 1-13。
for rank in hand:
count[rank] += 1
这是对数据的线性传递，O(N)。
现在，遍历计数数组，找到最长的 non-zero 值序列。这是一个包含 13 个元素的 fixed-length 列表，每个元素只接触一次：O(1)。如果你积累了一个倍数列表（卡计数，那么你最后也会有你的组合因子。
因此，生成的算法和代码是 O(N)。
例如，让我们将其缩短为 7 个牌值，0-6。给定输入整数
1 2 1 3 6 1 3 5 0
您完成了第一次计数项目：
[1 3 1 2 0 1 1]
第二次传递给你最大 运行 长度为 4，计数为 [1 3 1 2]。
您报告的 运行 为 4、三重和双倍，或者点数
4 * (1 * 3 * 1 * 2)
您还可以计算对值：
2 * 3! + 2 * 2!