函数的平均情况复杂度
假设以下函数的平均案例复杂度是多少输入是一组独立的统一自然数。
def d(a):
for i in range(len(a)):
if a[i] == 0 or a[i] == 1:
for j in range(i+1, len(a)):
if not (a[j] == 0 or a[j] == 1):
swap(a, i, j)
break
您认为如何用数学术语解决这个问题？
What is the average case complexity of the following function given that the input is a set of independent uniform natural numbers.
def d(a):
for i in range(len(a)):
if a[i] == 0 or a[i] == 1:
for j in range(i+1, len(a)):
if not (a[j] == 0 or a[j] == 1):
swap(a, i, j)
break
What do you think, how to approach this problem in mathematical terms?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
忽略所有细节，我们得到两个嵌套循环，表明二次算法。考虑到
if，只有一小部分数字实际执行内部循环，因此平均情况实际上是线性的。Leaving out all the details, we get two nested loops, indicating a quadratic algorithm. Taking the
ifinto account, such a small percentage of numbers actually execute the inner loop that the average case is effectively linear.结果将是
a的长度乘以range(len(a))中任何索引的平均时间（让我们忽略break目前）。对
a值的两次访问，因此我们添加2 * [检索 a[i]]的时间。a（无限集合的元素，ℕ）的值是任何有限集合（例如 {0,1}）的元素的概率无限接近于零。由于内部的进一步代码需要有限的时间，因此我们可以安全地忽略它。平均情况复杂度：
2 len(a) [检索 a[i]]∈θ(len(a))⊂O(len(a) ）。The result will be the length of
amultiplied with the average time for any index inrange(len(a))(let's ignore thebreakfor now).Two accesses of the values of
a, so let's add2 * [time to retrieve a[i]]. The probability that a value ofa(an element of an infinite set, ℕ) is an element of any finite set(such as {0,1}) is infinitely close to zero. Since the further code inside takes finite time, we can safely ignore it.Average case complexity:
2 len(a) [time to retrieve a[i]]∈Θ(len(a))⊂O(len(a)).