如果我知道 k <= n，我可以简化双变量算法的 运行 时间分析吗？
Can I simplify the running time analysis of a two-variable algorithm if I know k <= n?
我有以下算法：
def neat_algorithm(n, k):
assert k <= n
assert k > 0
sum = 0
for i in range(n):
for j in range(n):
sum += 1
for i in range(n-k,n):
sum += 1
乍一看，这个算法的运行时间好像是Θ(n^2)+Θ(k)，但是除非1≤k≤n，否则会失败，最坏的情况会发生如果 k = n。因为我知道关于 k 的这些事情，所以说最坏情况 运行 时间实际上是 Θ(n^2)+Θ(n) 或者更确切地说只是 Θ(n^2) 是正确的，还是我需要在语句中保留k运行次？
在这种特殊情况下，您可以简化 Θ(n2 + k) = Θ(n2)，因为 k ≤ n ≤ n2，所以 n2 项占主导地位。
一般来说，即使 0 < k ≤ n，也不应总是用渐近表示法中的 n 替换 k。例如，在长度为 n 的未排序数组中找到最大的 k 个元素的问题可以在 O(n log k) 时间内解决。如果您改写 O(n log n)，那么它仍然是一个有效的上限，但是当 k 与 n 相比较小时（在实际情况中通常如此），它是一个弱上限。如果您使用 Θ 表示法而不是 O 表示法，那么 Θ(n log n) 实际上对于 k 较小的情况是不正确的。
我有以下算法：
def neat_algorithm(n, k):
assert k <= n
assert k > 0
sum = 0
for i in range(n):
for j in range(n):
sum += 1
for i in range(n-k,n):
sum += 1
乍一看，这个算法的运行时间好像是Θ(n^2)+Θ(k)，但是除非1≤k≤n，否则会失败，最坏的情况会发生如果 k = n。因为我知道关于 k 的这些事情，所以说最坏情况 运行 时间实际上是 Θ(n^2)+Θ(n) 或者更确切地说只是 Θ(n^2) 是正确的，还是我需要在语句中保留k运行次？
在这种特殊情况下，您可以简化 Θ(n2 + k) = Θ(n2)，因为 k ≤ n ≤ n2，所以 n2 项占主导地位。
一般来说，即使 0 < k ≤ n，也不应总是用渐近表示法中的 n 替换 k。例如，在长度为 n 的未排序数组中找到最大的 k 个元素的问题可以在 O(n log k) 时间内解决。如果您改写 O(n log n)，那么它仍然是一个有效的上限，但是当 k 与 n 相比较小时（在实际情况中通常如此），它是一个弱上限。如果您使用 Θ 表示法而不是 O 表示法，那么 Θ(n log n) 实际上对于 k 较小的情况是不正确的。