为以下示例计算 Big "O"

Question

假设我有以下代码示例：

int number;
for(int i = 0; i < A; i++)
    for(int j = 0; j < B; j++)
        if(i == j) // some condition...
            do{
                number = rand(); 
            }while(number > 100);

我想知道这个例子的大“O”。外部循环是 O(A * B)，但我不确定如何看待 do-while 循环，它是大“O”。在最坏的情况下它可能是一个无限循环，在最好的情况下 O(1) 并被忽略。

编辑：更新了 if 语句中的条件（用简单的比较替换了函数调用）。

Answer 1

虽然rand()是一个随机函数并且它有一个指定的输出范围，但我们可以说do while语句是O(1)。所以，这取决于someCondition()函数。

总复杂度为 O(A * B) * O(someCondition)。

为以下示例计算 Big "O"

Calculating Big "O" for the following example

algorithm

big-o