给定算法的时间复杂度是多少？

Question

我们得到了我想出解决方案的问题。有人可以帮我确定给定解决方案的时间复杂度吗？应该是 O(n) 还是 O(n^2)？在我看来，它应该是 O(n)。

问题

编写一个程序，按照以下给定的条件打印数组元素的总和。

如果数组依次为 6 和 7，则忽略 6 和 7 之间的数字，并考虑其他数字进行总和计算。

Eg1) 数组元素 - 10,3,6,1,2,7,9 O/P: 22 [即 10+3+9]

Eg2) 数组元素 - 7,1,2,3,6 O/P:19

Eg3) 数组元素 - 1,6,4,7,9 O/P:10

解决方案

outer: for (i = 0; i < elementsCount; ++i) {
            if (arr[i] == 6) {
                int sumBetweenBounds = arr[i];

                for (j = i + 1; j < elementsCount; ++j) {
                    if (arr[j] == 7) {
                        i = j;
                        continue outer;
                    }

                    sumBetweenBounds += arr[j];
                }

                sum += sumBetweenBounds;
                continue;
            }

            sum += arr[i];
        }

Answer 1

在谈论时间复杂度时，我们应该区分最佳情况、最坏情况或平均情况（https://en.wikipedia.org/wiki/Best,_worst_and_average_case）。当未提及时，通常打算采用最坏的情况。

在最坏的情况下，您的算法是 O(n^2) 因为当数组元素为 6 时运行内部循环。在最坏的情况下，所有数组元素都可能是这个值。

在最好的情况下，它是 O(n)，但这通常并不有趣。

对于平均情况分析，您需要知道将运行您的算法的所有数组中的值分布。