这段代码的复杂性分析 [英] complexity analysis of this code

问题描述

分析以下代码并回答此算法的复杂性

"Analzying the following code and answer the complexity of this algorithm

public String getString()
String s= "";
for(int i =0 ; i < LARGE_NUMBER ; i++) {
s += "a"
}

推荐答案

我说的不仅仅是O（N），还不到O（N ^ 2）。



可能是因为字符串需要在某些时候重新分配并被复制。



如果字符串是一个STL字符串（例如），当它太小而无法为其添加新字母时，它将加倍（我认为）。



所以你将拥有：

：字符串大小= 0;

a：字符串大小= 1; //加倍大小并复制字符串。

aa：字符串大小= 2; //加倍大小并复制字符串。

aaa_和aaaa：字符串大小= 4; //加倍大小并复制字符串

aaaaa___，aaaaaa __，aaaaaaa，aaaaaaaa：字符串大小= 8; ...

。 ..



考虑一下。



如果你需要优化它，那么保留一个足够大的string以减少重新分配和复制新字符串的时间。

（技术性）在新的C ++中，字符串副本将通过使用move运算符来消除;所以你只需要提前调整字符串大小。



M

I'd say more than O(N), but less than O(N^2).

Probably because the string will need to be reallocated at some point and be copied.

If the string is a STL string (for example), its will be doubled (I think) when it is too small to add a new letter to it.

so you will have :
"" : string size = 0;
"a" : string size = 1; // double the size and copy the string.
"aa" : string size = 2; // double the size and copy the string.
"aaa_" and "aaaa" : string size = 4; // double the size and copy the string
"aaaaa___", "aaaaaa__", "aaaaaaa_", "aaaaaaaa" : string size = 8;...
...

think about it.

If you need to optimize this, than reserve a large enough string to reduce the number of time the new string will be re-allocated and copied.
(technicality) In the new C++ , the string copy will be mostly eliminated with the use of the "move" operator; so you will only have to resize the string in advance.

M

我认为它小于O（N ^ 2 ），因为它只包含1个for循环。

I think it's smaller than O(N^2), because it contains only 1 for loop.

依赖于String的实现。

如果string在开始时保持LARGE_NUMBER个内存字节，则复杂性为O （N）。

如果字符串每次扩大一个字节的内存并进一步重新定位，那么它是O（N ^ 2）。

当不知道大小时在使用它之前，你需要重新定位，然后你可以通过在容量不足时将内存大小加倍来加快速度。我认为它应该是O（log2（N + 1）），为追加操作添加O（N）。

deppends on implementation of String.
If string holds the LARGE_NUMBER of memory bytes at the start then complexity is O(N).
If string each time enlarges by one byte of memory with further relocation then it is O(N^2).
When there is not known the size before using it, and you need relocation then you can make it faster by doubling memory size when capacity is not enough. I think it should be something like O(log2(N+1)) with adding O(N) for append operation.

这篇关于这段代码的复杂性分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！