algorithm - 可以计算Shader算法的时间复杂度吗？

Question

我目前正在上一门算法分析课，我们需要进行小组作业。教授要求我们选择计算机科学中的某个领域，选择一种算法并证明渐近极限(至少 O(N))。

所以我和我的同事选择做一个计算机图形算法，更具体地说是一个光照体积算法。

但是算法分析书上分析的代码都是跑在CPU上的。在 OpenGL 中生成的代码在 GPU 上运行，不能保证线性度，因为它是由多个并行运行的其他 CPU 组成的。

这种行为会影响计算吗？有人可以帮我弄清楚从哪里开始吗？

这段代码摘自GPU Gems 3: Volumetric Light Scattering as a Post-Process .

float4 main(float2 texCoord : TEXCOORD0) : COLOR0  
{  
  // Calculate vector from pixel to light source in screen space.  
   half2 deltaTexCoord = (texCoord - ScreenLightPos.xy);  
  // Divide by number of samples and scale by control factor.  
  deltaTexCoord *= 1.0f / NUM_SAMPLES * Density;  
  // Store initial sample.  
   half3 color = tex2D(frameSampler, texCoord);  
  // Set up illumination decay factor.  
   half illuminationDecay = 1.0f;  
  // Evaluate summation from Equation 3 NUM_SAMPLES iterations.  
   for (int i = 0; i < NUM_SAMPLES; i++)  
  {  
    // Step sample location along ray.  
    texCoord -= deltaTexCoord;  
    // Retrieve sample at new location.  
   half3 sample = tex2D(frameSampler, texCoord);  
    // Apply sample attenuation scale/decay factors.  
    sample *= illuminationDecay * Weight;  
    // Accumulate combined color.  
    color += sample;  
    // Update exponential decay factor.  
    illuminationDecay *= Decay;  
  }  
  // Output final color with a further scale control factor.  
   return float4( color * Exposure, 1);  
}

我认为渐近极限是样本的函数。还需要考虑的是生成着色器所需的 4 个物理方程。在此先感谢所有社区的帮助!

Answer 1

算法的复杂性不会随着处理元素的数量而改变(对于有限数量的处理器)。多项式时间算法是多项式时间，无论是在CPU还是GPU上。换句话说，n² 与 (n/320)² 没有区别，因为“n”接近无穷大。

算法的复杂度不变； 执行时间。但很多复杂性都是如此。快速排序和合并排序具有相同的 nLog(n) 复杂度，但实际上快速排序平均更快。

渐近极限并不是性能的终极目标。