文件修改的时间复杂度？

Question

这些文件修改的时间复杂度（相对于文件大小）是多少？

我希望覆盖和附加都很快。如果文件的结构像 C++ 那样，我可以看到前置足够快deque，但我从未见过一种允许低级前置的语言。我怀疑在中间插入是否很快，尽管我想象有一些数据结构可以使它更快。

Answer 1

在大多数文件系统中：

插入的 O(n + m) 是最坏的情况。当您插入文件时，您必须将文件中当前的所有字节从插入点向下移动，以便为要插入的 n 个字节留出一个洞。所以如果你有：

This is a test system.

如果你想在“测试”后面插入“紧急广播”，那么你首先必须为插入的文本打一个洞：

This is a test                            system.

然后插入新文本：

This is a test of the emergency broadcast system.

这样，文件在概念上非常类似于数组。如果你想在前面或中间插入一些东西，你必须为它打一个洞。如果你想删除一些东西，你就必须填补空缺的空间。

有些文件系统可以让您将非连续块中的文件修补在一起。也就是说，你可以得到逻辑上类似的东西：

<pointer to "This is a test" chunk>
<pointer to "of the emergency broadcast" chunk>
<pointer to "system." chunk>

文件系统根据需要负责分割和合并块。这些文件系统并不罕见，但普通程序通常不会使用该功能。