为什么在循环O(n²)中添加不可变容器? [英] Why is addition of immutable containers in a loop O(n²)?

问题描述

我听说在循环中添加不可变字符串或其他包含多个项目的不可变(连续)容器可以是O(n²).例如

I have heard that adding immutable strings, or other immutable (contiguous) containers of multiple items, in a loop can be O(n²). For example

string = ""
repeat n times:
    string = string + "X"

这是为什么?

推荐答案

将长度为A的不可变连续容器添加到长度为B的容器中通常需要O(A+B)的时间.这是因为生成的容器将需要重新构建，并且其长度为A+B.

Adding an immutable contiguous container of length A to one of length B normally takes O(A+B) time. This is because the resulting container will need to be built anew, and is of length A+B.

考虑给定循环的第i次添加.该字符串的长度为i-1，并且您添加了长度为1的字符串.因此，所得的字符串以及所需的时间与i成正比.

Consider the ith addition of the given loop. The string will be of length i-1, and you add a string of length 1. The resulting string, and thus the time required, is therefore proportional to i.

因此，我们得到了总费用:

We therefore have the total cost:

1 + 2 + 3 + 4 + 5 + ... + n-2 + n-1 + n

= ∑i from i=1 to i=n

= ½n·(n+1)

= ½n² + ½n

，其顺序为O(n²).

之所以将它们指定为 contiguous 容器，是因为 some 不连续的不可变容器(例如二叉树)只能引用其他不可变容器，而不能复制它们，可以提高添加速度.

The reason these are specified as contiguous containers is because some non-contiguous immutable containers (like binary trees) can merely reference the other immutable containers instead of copying them, which can increase the speed of addition.

这篇关于为什么在循环O(n²)中添加不可变容器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！