论String操作时间复杂度

编译器优化之后两段代码应该是一样的执行效果吧？？？

for循环里面，编译器不会优化。

抛开楼主的问题不谈，弱弱的问个不相干的问题

拷贝一个数组，用循环和用System.arrayCopy或C的memcpy整段内存拷贝的时间复杂度是不是一样

映像中System.arrayCopy用的就是本地优化过的方法

时间复杂度是多少

我的直觉是O(1)。

O(1)的意思是，拷贝1个字节和拷贝1M字节所用时间是一样的，即，算法所用时间与数据量无关。
没有这么神奇的数组拷贝方法吧？

楼主两个算法，其中一个无论如何优化，每次循环应该都触发一次数组拷贝。
每次拷贝的时间复杂度为O(N)，而每次循环N都加1。
另一个算法由于使用了StringBuilder，如果不考虑自动扩展，就没有数组拷贝，但是至少还是要遍历一遍源字符串，所以时间复杂度是O(N)，即算法所用时间直接与源串长度相关。

搜索了一番，都说memcpy快到极致，拷贝1个字节和拷贝大批数据是一样的，“远低于printf等屏幕显示类函数，就算是空循环体的for循环再编译后也会产生若干行，比memcpy要慢”

O(1)的意思显然不是复制1字节和1M字节所用的时间都一样。为了方便你理解，HashMap里面只有1条数据，和有1M条数据时查找的时间是一样的吗？但是它是O(1)的。

以前研究过VC里面的实现，是把char*转换为int*来做memcmp或memcpy的，这样在32位系统里面有优势，可以做到一个机器指令就比较或者拷贝4个字节。但即使是这样，时间复杂度也是0(N/4)，还是受制于要拷贝的数据量。这个可以通过测试得到验证。

至于说“memcpy快到极致，拷贝1个字节和拷贝大批数据是一样的”，这个说法我还是第一次听到。虽然知道有些CPU有原生的数组操作指令（即数组的拷贝、比较等操作只需要一条机器指令），但实际上还是需要多次访问内存或L1/L2缓存，如果数据量超过L1/L2缓存，就会涉及多个指令周期的问题。基于这个原理，我还是无法理解这种说法。

不过我始终坚信IT里面是没有魔法的。


楼主的问题里面，涉及到Java的运行时优化。由于String是final，优化做到极致，是可以达到等于第二种的性能的。但是在不优化的情况下，第个方法里面生成新的String时，必然涉及到数组拷贝操作。