I/O复杂度与空间复杂度与时间复杂度

Question

我很难理解I/O复杂性与空间复杂性与时间复杂性之间的术语。

我知道什么是时间复杂性。但是，I/O复杂性和空间复杂性是一回事吗？

谢谢你提前给我答案。

Answer 1

我的理解如下：

1. 时间复杂度表示操作(运行时)的增长
2. 空间复杂度表示内存使用量的增长。
3. I/O复杂性表示I/O操作(运行时)的增长

是的，time和I/O是相似的。不同的是，ALU指令比I/O快得多(在旧架构上并非如此，I/O复杂性被忽略了)。因此，如果您同时计算某项内容或将其划分为需要使用I/O存储/重新存储子结果的子块，则情况就不一样了。时间复杂度是相同的，但是I/O复杂度如果不小心的话，也不会对运行时产生很大的影响。

例如，OpenGL的常见错误是将纹理加载到GPU每个帧，而不是只加载一次。它可以被认为是I/O操作，即使它是内存传输(通常使用DMA)。渲染时间的复杂性是一样的..。但I/O不是，fps可能会显著下降。如果你有很多纹理，你可以按需加载它们(不是每帧，而是每一层，建筑，地图的一部分等等)因此，fps仍然很高，但以游戏/级别/级别之间的负载时间为代价。同样的原则也适用于任何I/O相关的东西，而不仅仅是图形.