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

Question

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

喜欢这个例子

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 可能实际上使用了更多步骤，因为它被编码为处理任意数量位置的旋转，这比始终只旋转一个位置稍微多一些工作像您的代码一样放置。另一方面，旋转一个位置也很常见，标准库可以检查这一点，并针对特定情况使用与您的类似的代码。