operating-system - 当程序或数据被分区时，什么样的程序不能保持其复杂性结构？

Question

我在操作系统课上收到了这个问题，经过一些研究，我仍然找不到这个问题的答案。

标签： operating-systemtime-complexitycomplexity-theorypartition

Answer 1

我将复杂性结构理解为计算给定数据或程序分区级别所需的最小复杂性（计算步骤数）。

答案就在问题中，即需要更多步骤来处理分区数据或处理单元的程序。

1. 如果数据访问模式（粒度、范围、基数）需要访问和集成结果。
2. 访问和集成计算划分的产品（线程、进程、节点）（IO、集成）

具有 X 级复杂性的程序，同时利用对数据的所有部分和粒度的索引访问。如果对数据进行分区，则需要更多步骤来单独访问和查询分区 Y，还需要更多步骤来集成 W，从而导致 f(X, Y, W) 级别的复杂性取决于集成和访问的级别。

一个例子是执行表连接查询的程序，通过索引优化搜索（SQL 连接）。如果表或列位于不同的数据库或节点中（NoSQL(Key value, Columnar ...)），则此类程序无法保持相同的复杂性操作。

另一个例子是程序调用（线程、进程、节点）并组合结果。调用线程并组合结果将比顺序执行更多的计算步骤。

这个问题有点脱离上下文，你最好添加上下文！