本文介绍了这段代码的复杂性分析的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
分析以下代码并回答此算法的复杂性
"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.
更多推荐
这段代码的复杂性分析
发布评论