更新：我非常喜欢这个问题，我只是写了博客。请参阅字符串、不变性和持久性

简短的回答是： 如果 n 没有变大，则 O(n) 是 O(1)。 大多数人从微小的字符串中提取微小的子字符串，因此复杂性如何渐近增长
完全无关紧要 。

长答案是：

一个不可变的数据结构被构建为使得一个实例上的操作允许重新使用原始内存，只需要少量（通常为 O(1) 或 O(lg
n)）的复制或新分配，称为“持久”不可变的数据结构。.NET 中的字符串是不可变的；您的问题本质上是“他们为什么不坚持不懈”？

因为当您查看 通常 在 .NET 程序中对字符串执行的操作时，简单地创建一个全新的字符串 在所有相关方面都几乎没有更糟。
构建复杂的持久性数据结构的费用和难度并不能收回成本。

人们通常使用“子字符串”来提取一个短字符串——比如说，十个或二十个字符——从一个稍长的字符串中——可能是几百个字符。您在逗号分隔的文件中有一行文本，并且您想要提取第三个字段，即姓氏。该行可能有几百个字符长，名称将是几十个。在现代硬件上，五十字节的字符串分配和内存复制
速度惊人。 制作一个由指向现有字符串中间的指针加上长度组成的新数据结构 也 非常快是无关紧要的。“足够快”顾名思义就是足够快。

提取的子串通常体积小，寿命短；垃圾收集器很快就会回收它们，而且它们一开始并没有在堆上占用太多空间。因此，使用鼓励重用大部分内存的持久策略也不是胜利；你所做的只是让你的垃圾收集器变慢，因为现在它不得不担心处理内部指针。

如果人们通常对字符串执行的子字符串操作完全不同，那么采用持久方法是有意义的。如果人们通常有数百万个字符的字符串，并且正在提取数千个大小在十万个字符范围内的重叠子字符串，并且这些子字符串在堆中存在很长时间，那么使用持久子字符串将是非常有意义的方法;
不这样做是浪费和愚蠢的。但是 大多数业务线程序员不做任何事情，甚至模糊地喜欢那些事情. .NET 不是为人类基因组计划的需求量身定制的平台；DNA
分析程序员每天都必须解决这些字符串使用特性的问题；你不这样做的可能性很大。少数确实构建了与 他们的 使用场景密切匹配的持久数据结构的人。

例如，我的团队编写的程序可以在您键入 C# 和 VB 代码时对其进行即时分析。其中一些代码文件非常 庞大 ，因此我们无法进行 O(n)
字符串操作来提取子字符串或插入或删除字符。我们构建了一堆持久的不可变数据结构，用于表示对文本缓冲区的编辑，使我们能够快速有效地重用大量现有字符串数据
以及 对典型编辑的现有词法和句法分析。这是一个很难解决的问题，它的解决方案是针对 C# 和 VB
代码编辑的特定领域量身定制的。期望内置的字符串类型为我们解决这个问题是不现实的。