计算使用 C++ std 函数而不是 for 循环的 Big O

Question

如果我正在实现一个 for 循环以在数组中的两个索引之间向右移动元素，那么我需要 O(n) 来移动这些元素，但是如果我使用像 [=12 这样的库函数呢？ =] 一步执行，所以这意味着它花费了常数时间。

喜欢这个例子

vector<int> arr = {1,2,3,4,5,6,7,8,9,10};

int temp = arr[5];

for(int i = 5 ; i >= 3 ; i--){


    arr[i]=arr[i-1];

}

arr[2] = temp;

所以 arr 将是 {1,2,6,3,4,5,7,8,9,10}

相反，我可以

 rotate(arr.begin()+2,arr.begin()+5,arr.begin()+6);

...这将导致相同的移位数组

但是第一个大约需要 3 步，另一个只需要 1 步，是这样吗？

Answer 1

std::rotate 具有线性复杂度，因此虽然它可能比您的代码稍快或稍慢，但两者使用的步骤数大致相同。

在这种特殊情况下，std::rotate 可能实际上使用了更多的步骤，因为它被编码为处理任意数量的位置的旋转，这比总是像您的代码那样只旋转一个位置稍微多一些工作做。另一方面，也有可能旋转一个位置很常见，标准库可以检查这一点，并针对特定情况使用与您的相似的代码。

Answer 2

不，它确实需要线性 time.Actual 时间复杂度是初始节点和最终节点之间的差异。查看 https://en.cppreference.com/w/cpp/algorithm/rotate

calculating the Big O of using C++ std function instead of for loop