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

我现在在上算法分析课
学科小组工作。教授要求我们选择计算机科学的某个领域，选择一个算法并证明渐近极限（至少O（N））。
所以我和我的同事选择做一个计算机图形学算法，更具体地说是一个光照体积算法。
但是算法书上分析的所有代码都是在CPU上运行的OpenGL生成的代码是在GPU上运行的，由于它是由多个并行运行的cpu构成的，因此不能保证线性度。
这种行为会影响计算吗？有人能帮我弄清楚从哪里开始吗？
这段代码是从NVIDIAs网站提取的：
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch13.html

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个物理方程。提前感谢所有社区的帮助！

最佳答案

算法的复杂性不会随着处理元素的数量（对于有限数量的处理器）而改变。多项式时间算法是多项式时间，无论是在cpu上还是在gpu上。换言之，当“n”接近无穷大时，n2与（n/320）2没有区别。
算法的复杂性不会改变，执行时间会改变。但这是非常复杂的。快速排序和归并排序具有相同的nlog（n）复杂性，但快速排序在实践中平均更快。
渐近极限并不是全部性能的终结。