这段代码的复杂性分析

本文介绍了这段代码的复杂性分析的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

"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.