我需要帮助解决一个问题。我刚刚开始阅读有关O符号的内容，但在分析代码时我还是新手。
所以这就是问题所在：
给出以下伪代码，其中A是数字字段，其索引1到长度（A）的元素可以被访问。我是由整数组成的，所以除法的结果是向下舍入的。 SkipPrint功能的复杂性是什么？
1: procedure SkipPrint(A)
2: i <- length(A)
3: do
4: print(A[i])
5: i <- i/2
6: while i>0
所以我认为复杂度O（n）因为函数需要通过数组而只需要一次，对吧？ （第2行）每隔一行的幅度较小，因此保持O（n）？
提前致谢。非常感谢您的帮助。
健康
这将是O（n），是的。你是对的。这是因为有一个循环在一个方向上迭代。 （在这种情况下，i总是变小）
让我们说n = length(A)并假设我们在更简单的情况下length(A) = 2^m，对于一些整数m。
然后i，在每一步都减半，将具有以下价值：
2^m, 2^{m-1}, 2^{m-2}, ..., 2, 1, 0
这表明循环将运行m次，直到i到达0。从n = 2^m，这意味着m = lg n因此复杂性是O(lg n)。
在一般情况下，定义m := floor(lg n)。上面的分析表明，循环将迭代m次，直到i变为0。因此，复杂性将是O(floor(lg n))，与O(lg n)相同。