平均时间和 Space 复杂度

Question

我有一个等式 cValues[i++] = (sum += d) / ++count; 但是如果计数大于或等于 window 大小，则计数可以受到 window 大小的限制，因此等式有可能成为 cValues[i++] = (sum += d) / windowSize; window大小不变。根据我对这个区域的观察，当它达到 window 大小时，是 O(n) 然后是 O(1)。
我猜的 space 复杂度也是 O(n)。

整个方法是这样的：

 double[] CMA(int windowSize, double[] values)
        {
            //size of array determined by user
            double[] cValues = new double[values.Length];
            //index
            int i = 0;
            foreach (var d in values)
            {
                if (count >= windowSize)
                {
                    cValues[i++] = (sum += d) / windowSize;
                }
                else if (count < windowSize)
                {
                    cValues[i++] = (sum += d) / ++count;
                }

            }

            return cValues;
        }

值可以是任何类型的双精度数，负数或正数。

Answer 1

问题的答案是因为我们可以有负数，所以我们有可能永远不会超过 windowSize，因此达到 count 是一个完全可能的情况，所以，及时这是在）。就space的复杂度而言，你理解的是整个函数的O(n)，但是实际的算法，也就是

            foreach (var d in values)
            {
                if (count >= windowSize)
                {
                    cValues[i++] = (sum += d) / windowSize;
                }
                else if (count < windowSize)
                {
                    cValues[i++] = (sum += d) / ++count;
                }

            }

部分不分配新元素。初始化阶段负责整个 space 复杂性。