成本的算法

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)