|
锁定老帖子 主题：论String操作时间复杂度
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2013-05-22
@mike.liu
引用 忽略抽象语句本身有时间复杂度问题，会使算法时间复杂度的分析失去其意义。 同一段代码，你找个286机器运行和找个大型机运行，你觉的时间会是一样的吗。所以，讨论具体代码的执行时间没有意义，只有把它放到具体的环境中讨论才行。譬如比较for(1..100)在大型机上的执行时间和for(1..1000)在286上的执行时间。 因此，要讨论算法的复杂度怎么办，必须要抽象。for(1..100)和for(1..10000)的时间复杂度相同，都是O(N)。这样就忽略了具体的环境因素。 《计算机程序设计艺术》中 引用 只记得里面作者自己定义了一套类似机器指令的东西，每条指令都是一个时间单位。然后他所有的算法都是基于这套机器指令集。这样，每个算法要执行多少步是明确的，所以在他那里定义的时间复杂度是明确的 实际上也是做的这个事情，把环境因素忽略。这不就是抽象吗？ |
| 返回顶楼 | |
|
发表时间：2013-09-02
406657836 写道 时间复杂度都是O(N)，空间复杂度就完全不一样了。
在for里面用+号是每次new 一个StringBuilder(); 可以想象下 如果for足够多的时候要new多少个临时对象。 这个对gc来说是一个悲剧。 下面这个new StringBuilder 没有指明容量。 那么扩容也是一个悲剧，每次扩容是上次的2倍。 所以如果事先估计一下String的容量就尽量给一个初始值。默认是16这个是很短的。 就如本题可以让初始容量为100。否则在for里面要面临3次扩容。 另外有人在回复的时候建议用StringBuffer。 在本题中明显没有并发，不要用StringBuffer.加锁也是影响性能的。 说的挺好的 补充 用+号不仅会new StringBuffer，而且在每次赋值时候都会new String，循环里写成java应该是这样了
String s = "";
for() {
String str = String.valueOf("a");
StringBuffer sb = new StringBuffer(s);
sb.append(str);
s = sb.toString();
}
另外扩容并不是2倍,而是2倍+2 (有点较劲了...见谅) |
| 返回顶楼 | |
