STL的partition算法复杂度问题
这个算法的源码我大致改了下。
int * partition(int * First, int * Last, _Pr _P)
{
for (; ; ++First)
{
for (; First != Last && _P(*First); ++First)
;
if (First == Last)
break;
for (; First != --Last && !_P(*Last); )
;
if (First == Last)
break;
iter_swap(First, Last); //交换2个指针的值
}
return (First);
}
第三个参数传递一个函数对象，这里可以认为是一个返回类型为BOLL的函数指针。问题与此无关。
大FOR循环里的2个FOR循环都没有语句体。都是指针的滑动运算。
这个算法的时间复杂度是多少？可以给出算法复杂度的分析吗？
[解决办法]
显然O(n)啊。First一直往右，Last一直往左，直到两个相遇退出。就线性了。
