我知道使用toString()方法将合适的对象(例如，链表)转换为字符串是O(n)操作，其中'n'是链表的长度。然而，如果你想用replace()方法替换字符串中的一些东西，这也是一个o(k)方法吗，其中k是字符串的长度?
例如，对于行String str = path.toString().replace("[", "").replace("]", "").replace(",", "");，它是否遍历链表的长度1次，然后再遍历字符串的长度3次?如果是这样，是否有更有效的方法来完成这行代码的工作?
是的。replace不知道[和]只存在于起点和终点。实际上，情况更糟——你会得到另一个用于复制字符串的循环(字符串有一个底层数组，需要整个克隆以去掉其中的一个字符)。
如果你的意图是替换字符串中的每个[，那么，不，没有更快的方法。但是，如果您的实际意图只是简单地没有左大括号和右大括号，则可以编写自己的循环来toString内容。比如:
LinkedList<Foo> foos = ...;
StringBuilder out = new StringBuilder();
for (Foo f : foos) out.append(out.length() == 0 ? "" : ", ").append(f);
return out.toString();
甚至:
String.join(", ", foos);
甚至:
foos.stream().collect(Collectors.joining(", "));
这些都与.replace("[", "")不同——毕竟，如果[符号是任何Foo对象的toString()的一部分，那么它也会在.replace("[", "")中被剥离——尽管您可能不希望发生这种情况。
请注意，现代cpu的工作方式，除非列表中有超过几千个元素，否则循环4次基本上是免费的，并且不需要可测量的时间。在一定数量的循环后，O(n)的概念便会"发挥作用"。在现代硬件上，它往往是许多循环才起作用。通常其他问题要重要得多。举个简单的例子，链表，一般来说?与ArrayList之类的东西相比，性能很差。即使在0 (k)的情况下它也应该更快。这是由于链表创建额外对象的方式，以及这些对象往往是不连续的(在内存中彼此不靠近)。现代cpu根本不能读取内存。它们可以要求内存控制器取一个片内缓存页，并用另一个内存页的内容替换它，这需要500到1000个周期。CPU将要求内存控制器这样做，然后进入睡眠状态1000个周期。您可以看到，减少这样做的次数可以对性能产生相当显著的影响，然而O(k)业务没有也不能考虑到这一点。
不要担心性能，除非你有一个实际的场景，程序的运行速度比你想象的要慢。然后，使用分析器找出哪1%的代码消耗了99%的资源(因为实际上总是有1%的"热路径"起作用)，然后优化这1%。几乎不可能预测1%的人会是什么。因此，在编写代码时不要尝试这样做，这只会导致您编写更难维护、更不灵活的代码——具有讽刺意味的是，这往往会导致调整热路径更困难的情况。从本质上讲，担心性能，会减慢代码的速度。因此，不要担心这些问题，而应该关注那些易于阅读和修改的代码。