算法複雜度與輸入量有關系?我們先來看下面一段代碼:int cnt = 1; while (cnt < n) { cnt *= 2; //時間複雜度為O(1)的程序步驟序列 } ，下面我們就來聊聊關于算法複雜度與輸入量有關系?接下來我們就一起去了解一下吧!

算法複雜度與輸入量有關系

我們先來看下面一段代碼:

int cnt = 1; while (cnt < n) { cnt *= 2; //時間複雜度為O(1)的程序步驟序列 }

由于cnt每次在乘以2之後都會更加逼近n，也就是說，在有x次後，cnt将會大于n從而跳出循環，所以$2 ^ x = n$, 也就是$x = log_2n$，所以這個循環的複雜度為O(logn)

$c$ 常數 $logN$ 對數級 $log ^ 2N$ 對數平方根 $N$ 線性級 $NlogN$ $N ^ 2$ 平方級 $N ^ 3$ 立方級 $2 ^ N$ 指數級

由此我們可以得知，$logN$的算法效率是最高的

1.對分查找

- (int)BinarySearch:(NSArray *)originArray element:(int)element { int low, mid, high; low = 0; high = (int)originArray.count - 1; while (low <= high) { mid = (low high) / 2; if ([originArray[mid] intValue] < element) { low = mid 1; } else if ([originArray[mid] intValue] > element) { high = mid -1; } else { return mid; } } return -1; }

2. 歐幾裡得算法

- (unsigned int)Gcd:(unsigned int)m n:(unsigned int)n { unsigned int Rem; while (n > 0) { Rem = m % n; m = n; n = Rem; } return m; }

3.幂運算

- (long)Pow:(long)x n:(unsigned int)n { if (n == 0) { return 1; } if (n == 1) { return x; } if ([self isEven:n]) { return [self Pow:x * x n:n / 2]; } else { return [self Pow:x * x n:n / 2] * x; } } - (BOOL)isEven:(unsigned int)n { if (n % 2 == 0) { return YES; } else { return NO; } }

在$$庫裡有log()函數和log2()函數

log()函數的底數默認為自然對數的底數e

log2()函數的底數很顯然就是2咯qwq

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; //#define DEBUG(x) cerr << #x << "=" << x << endl int main() { cout << log(M_E) << endl; cout << log2(2) << endl; return 0; }

然後我們就會得到

1 1

的結果

$$庫裡有兩個常量M_E和M_PI M_E代表的是自然對數的底數e M_PI代表的是圓周率π

當題目的數據範圍達到了$10^{18}$的時候，很顯然就要用O(logn)的算法或數據結構了

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!