Algorithmic complexity O(logn) in detail

I. O(logn) code small proof

Let's start with the following code:

int cnt = 1;

while (cnt < n)
{
    cnt *= 2;
    //Sequence of Program Steps with Time Complexity O(1)
}

Since cnt is more approximate to n every time it multiplies by 2, that is to say, after X times, cnt will be larger than N and jump out of the loop, so (2 ^ x = n), that is, \(x = log_2n), the complexity of the loop is O(logn).

Typical time complexity

$c$ constant
$logN$ Logarithmic level
$log ^ 2N$ Logarithmic square root
$N$ Linear level
$NlogN$
$N ^ 2$ Square level
$N ^ 3$ Cubic level
$2 ^ N$ Exponential level

From this we can know that the efficiency of(logN) algorithm is the highest.

3. Common (logN) algorithm

1. Bifurcation Search

- (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. Euclidean algorithm

- (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. power operation

- (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;
    }
}

4. $library log function

There are log() and log2() functions in the $library

The base of log() function defaults to the base of natural logarithm e

The bottom number of the log2() function is obviously 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;
}

And then we'll get it.

1
1

Result

There are two constants M_E and M_PI in the $library
M_E represents the base number e of natural logarithms
M_PI stands for pi

Finally, it's the most basic and important thing.

When the data range of the topic reaches \(10 ^{18}), it is obvious that the O(logn) algorithm or data structure will be used.

Tags: C

Posted on Sat, 12 Oct 2019 09:19:54 -0700 by The Chancer