java - Java中字符串连接的计数操作
问题描述
我试图理解为什么字符串连接是O(n)
Java 中的时间复杂度。我们被告知这s1 + s2
将创建一个长度为 的新字符串s1.length() + s2.length()
,并将其复制s1
到s2
该新字符串中。因此(由他们)计算了以下成本2 + 2(n+1) + 1
=>(5 + 2n)
我不确定我是否理解我的讲师是如何计算出来的。有人介意向我解释证明上述成本合理的字符串连接操作吗?
解决方案
我会小心地对 Java 中字符串连接期间发生的情况做出假设,因为它从 Java 9 开始在内部发生了变化。
关于这个主题的一个很好的介绍可以在这里找到:https ://www.javaspecialists.eu/talks/pdfs/2018%20Voxxed%20in%20Thessaloniki,%20Greece%20-%20%22Enough%20java.lang.String%20to %20Hang%20Ourselves%20...%22%20by%20Heinz%20Kabutz.pdf
也值得一读:https ://dzone.com/articles/jdk-9jep-280-string-concatenations-will-never-be-t
已经有点老了,但可能与你有关:https ://stackoverflow.com/a/15401136/875083