c++ - 算法成本

Question

接下来的问题是:

我们想知道 vector 的大小，我们不能使用 size() 但我们有一个函数 inBounds(vector& arr,int index) 如果索引有效则返回 true vector 的位置。

因此，我的方法是迭代位置。从 1 开始并重复 (2,4,8,16,32...) 直到 inBounds 返回 false，退后一步并在子范围内重复搜索。

举个例子，N = 21:

• 1 = 正确
• 2 = 正确
• 4 = 正确
• 8 = 正确
• 16 = 正确
• 32 = 错误

回到16，在16-32范围内搜索:

• (16+1) = 真
• (16+2) = 真
• (16+4) = 真
• (16+8) = 假

回到 20 (16+4) 并重新开始:

• (20+1) = 真
• (20+2) = 假

21 年后重新开始:

• (21+1) = 假

好的，所以大小是 21。

这是我在代码中的实现:

#include <iostream>
#include <vector>
using namespace std;

int inBounds(const vector<int>& arr,int i)
{
    return i < arr.size();
}

int size(const vector<int>& arr)
{
    int init = 0;

    while (inBounds(arr,init))
    {
        int start = 2;
        while (inBounds(arr,init+start))
        {
            start *= 2;
        }
        start /= 2;
        init += start;
    }
    return init;
}


int main()
{
    vector<int> arr;

    for (int i = 0;i < 1000;i++)
    {
        arr.resize(i);
        int n = size(arr);
        if (n != arr.size())
            cout << "FAIL " << arr.size() << ' ' << n << endl;
    }
    return 0;
}

这很好用。但我不知道这个算法的确切成本。第一次搜索确实是 log(N)，但现在我需要添加子范围搜索。所以我对实际成本有疑问

Answer 1

实际上，您的最坏情况是 O(log(n)²)(这有点符合预期，因为您有一个 O(log) 循环嵌套在另一个日志循环中)

要了解原因，请尝试缩小 31(一般情况下为 2^N-1)

我们举个例子，设N = 31:

1 = True
2 = True
4 = True
8 = True
16 = True
32 = False

O(log(N)) 到这里，好吧，没有人质疑

--

现在计算额外的步骤

回到16，在16-32范围内搜索:

(16+1) = True
(16+2) = True
(16+4) = True
(16+8) = True
(16+16) = False 

(4+1) 步 - 即 log(32/2)+1 = log(32)

24 岁后退一步

(24+1) = True
(24+2) = True
(24+4) = True
(24+8) = False

(3+1) 步 - 即 log(16/2)+1=log(16)

在 28 点后退:

(28+1) = True
(28+2) = True
(28+4) = False

(2+1) 步 - 即 log(8/2)+1=log(8)

30岁后退一步

(30+1) = True
(30+2) = False

(1+1)步即log(4/2)+1=log(4)

结果:(4+3+2+1=10 步正 + 4 步负)。或者，以另一种形式 log(32)+log(16)+log(8)+log(4)+log(2) - 1 =log(32)(1+1/2+1/3+ 1/4+1/5)-1。忽略最后的 -1，你的公式变成类似

log(N)*(1+1/2+1/3+1/4+...+1/N)

嗯，对于大的 N-es，harmonic series是发散的，渐近行为是 logarithmic .

所以你得到了一个不错的 O(log(N)*log(N)) 复杂度。

QED(??)