algorithm - 无法为 while 和 if 语句找到正确的 Big O

Question

    int i=0;
    while(i < N){
        if(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){
            // swap 
            int tmp = nums[i];
            nums[i] = nums[tmp - 1];
            nums[tmp - 1] = tmp;

        } else {
            i++;
        }
    }

我很困惑如何为这个算法找到正确的 Big O。
尽管我们将使用 while 循环执行总共 N 次，
如果 nums[i] 满足 if 语句的条件，我们将重复交换，直到我们不满足 if 语句。

我们可以说这个的时间复杂度是 O(N) 吗？
或者最坏的情况是 O(N^2)？

Answer 1

我同意这个问题没有明确定义。也许 OP 没有包含一些上下文。看完代码后，很明显这是一个排序算法(一个奇怪的算法)。顺便说一句，它访问数组索引的方式，我认为算法期望大小为 N 的数组 nums 填充 1...N 的整数，不一定按顺序并且可以重复。

关于 SomeWittyUsername 的观点，我们只是为了这个原因说元素不会导致无限循环等。

我对代码做了一个简短的注释。

int i=0;
    while(i < N){
        if(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){ // 1) check if it's in the right place 2) check if the potential swap will have no effect because of a repeat.

            // Swap nums[i] with nums[nums[i]-1]
            // Why swap these two values? 
            // This effectively places num[i] where it should be in the array

            int tmp = nums[i];
            nums[i] = nums[tmp - 1];
            nums[tmp - 1] = tmp;

        } else {
            // The element is in the correct spot
            i++;
        }
    }

看起来最好的情况 nums 最初是排序的，算法在 O(N) 时间内运行。

但由于大 O 表示法应该指的是最坏情况……我的最佳答案是:它也是 O(N)，但系数更高。它不是 O(N^2)，因为每次遇到放错位置的元素时，它都会将其放在正确的位置。