时间戳

首页 > 解决方案 > 计算使用 C++ std 函数而不是 for 循环的大 O

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

问题描述

如果我正在实现一个 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 步，是这样吗？

标签： c++algorithmtime-complexitystd

解决方案

std::rotate具有线性复杂性，因此虽然它可能比您的代码稍快或稍慢，但两者使用大约相同数量的步骤来完成这项工作。

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

推荐阅读