成本的算法

Question

的问题是下一个：

我们想知道一个向量的大小，我们不能使用大小（），但我们有一个函数界外球（矢量&改编，INT指数）如果索引是向量的有效位置，则返回true。

所以，我的方法是迭代位置。从1开始并复制（2,4,8,16,32 ...），直到inBounds返回false，退回，然后在子范围内重复搜索。

让我们做一个例子，把N = 21：

• 1 =真
• 2 =真
• 4 =真
• 8 =真
• 16 =真
• 32 =假

Step ba CK至16，和在16-32范围查询：

• （16 + 1）= TRUE
• （16 + 2）= TRUE
• （16 + 4）= TRUE
• （16 8）= FALSE

步骤返回到20（16 + 4），并开始了：

• （20 + 1）= TRUE
• （20 + 2）= FALSE

在21重新开始：

• （21 + 1）= FALSE

好了，所以大小为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; 
} 

这很好用。但是我不知道这个算法的确切成本。第一次搜索确实是日志（N），但现在我需要添加子范围搜索。所以我有我的怀疑关于真正的成本

Answer 1

其实，你的最坏的情况是O（日志（N））（这是八九不离十意料之中的，因为你有一个O(log)循环嵌套在另一个循环日志）

要了解原因，尝试来缩小31（2 ^ñ -1在一般情况下）

让我们做一个例子，把N = 31：

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

O（日志（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 =日志（32）

在24

步骤背面0

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

（3 + 1）的步骤 - 这是log（16/2）+ 1 =日志（16）

步骤回到28：

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

（2 + 1）步 - 这是log（8/2）+ 1 =日志（8）

在30

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

（1 + 1）的步骤。步骤背面这是log（4/2）+ 1 =日志（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（??）

Answer 2

似乎你的第一个子范围搜索也是logN（因为它使用基本相同的算法作为初始部分），而最终的子范围搜索是线性的（遍历每个值），但它是非常有界，只有N的一小部分。我会说你的算法大致是c * logN，其中c是一个小数值，代表你正在做的子半群的数目，所以一般来说O（logN）。

Answer 3

一旦你找到了上限，你应该做一个二分查找。适用于你的例子：

• 结果初始循环：16→真，32→假的，所以大小（16，32]

的二进制搜索总是要测试，最大的发现真正的中间和最小的发现假：

• 24→假=>（16，24]
• 20 - 真=>（20，24]
• 22→假=>（20，22]
• 21→假=>（20，21]

所以大小为21。

注意，这仅需要4个附加的测试，而不是7为你的算法。

Answer 4

假设矢量的大小为N = 31，因为这将是对你的算法在这里最坏的情况是如何将工作：

first pass : 1,2,4,8,16,32   [ total = 6 ] 
second pass: 17,18,20,24,32   [ total = 5 ] 
third pass : 25,26,28,32    [ total = 4 ] 
forth pass : 29,30,32     [ total = 3 ] 
fifth pass : 31      [ total = 1 ] 

如果我们在N.方面讲这将是：

T(N) = logN*(1+1/2+1/4+1/8+....) 

这是为了：(logN)^2

你实际上应该考虑@celtschk给出的方法，它是O(logN)