algorithm - 什么是输出敏感算法？

Question

这些算法中有哪些是输出敏感的？（他们的基本算法）

1. 光线追踪

2. gpu渲染

3. 喷溅

我们如何使用加速方法使它们可能对输出敏感？

我认为光线追踪和 gpu 对输出不敏感。

Answer 1

http://en.wikipedia.org/wiki/Output-sensitive_algorithm

For the folks who didn't understand the question, in computer science, an output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of or in addition to the size of the input.

Ray Tracing is output sensitive, in fact many ray tracing programs can generate smaller size images or movies in faser time.

GPU rendering is output sensitive, the fact that the GPU can parallelise the task, can speed up, but far less computations are required to render a smaller size image than a bigger one.

Texture splatting, is also output sensitive, since typically textures are repeated, so you can generate a huge image joining many of them, thus requiring more cpu power (and memory).