运行次数为常数的循环是否被认为是 Big - Oh(1)？

Question

根据流行的定义，运行固定次数的循环或递归也被视为 O(1)。

例如下面的循环是 O(1)

// Here c is a constant   
for (int i = 1; i <= c; i++) {  
    // some O(1) expressions
}

如果循环变量递增/递减恒定量，则循环的时间复杂度被视为 O(n)。

例如，以下函数的时间复杂度为 O(n)。

// Here c is a positive integer constant   
for (int i = 1; i <= n; i += c) {  
    // some O(1) expressions
}

我对以下示例有点困惑让我们取 c = 5 并且根据 O(1) 定义，下面的代码变为 - O(1)

for(int i = 0; i < 5 ; i++){
    cout<<"Hello<<endl";
}

函数 1：

for(int i = 0; i < len(array); i+=2){
    if(key == array[i])
         cout<<"Element found";
}

函数 2：

for(int i =0;i < len(array) ; i++){
    if(key == array[i])
        cout<<"Element found";
}

但是当我们比较上面的两个例子时，它们会变成 O(n) 还是第一个函数从定义上看是 O(1)。一个循环究竟是什么运行常量时间意味着?

Answer 1

假设 len(array) 就是我们所说的 b [*]，你的两个函数都是 O(n).

函数 2 将执行 if n 次（对数组的每个元素执行一次），显然是 O(n).

另一方面，函数 1 将执行 if n/2 次（数组中每隔一个元素执行一次），导致运行次 O(n*1/2)，并且由于常数因子（在本例中为 1/2）通常在 O 表示法中被省略，所以您将再次以 O(n).

结束

[*] 为了完整起见，如果你的数组是固定大小的，即。 len(array) 是一个常数，而不是两个函数都是 O(1).

Answer 2

"Loop running a costant number of times" 表示循环运行的次数从上方受常数限制，即给定的 独立于程序输入的数字 . 在函数 1 和 2 中（除非数组的长度是固定的，或者你可以证明它们永远不会大于特定常数，独立于输入）if 将执行一定次数，具体取决于关于输入的大小，所以时间复杂度不能是 O(1)。 "Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount" 是误导性定义

运行次数为常数的循环是否被认为是 Big - Oh(1)？

Is a loop that is running a constant number of times considered Big - Oh(1)?

algorithm

big-o

loops

函数 1：

函数 2：

运行 次数为常数的循环是否被认为是 Big - Oh(1)？

Is a loop that is running a constant number of times considered Big - Oh(1)?

algorithm

big-o

loops

函数 1：

函数 2：

运行次数为常数的循环是否被认为是 Big - Oh(1)？