算法之路(二)呈现O(logN)型的三个算法典型时间复杂度

典型时间复杂度

我们知道算法的执行效率,可以从它的时间复杂度来推算出一二。而典型的时间复杂度有哪些类型呢?

典型的时间复杂度.png

由上图,可以看出,除了常数时间复杂度外,logN型的算法效率是最高的。今天就介绍三种非常easy的logN型算法。

对分查找

给定一个整数X和整数A0,A1,...,An-1,后者已经预先排序并在内存中,求是的Ai= X的下表i,如果X不在数据中,则返回i = -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;
}

** 分析 :**通过上面的程序可以看出,要算出时间复杂度,就是求出while循环的次数。 mid 每次的取值分别是数组长度(N-1)/2,(N-1)/2/2,(N-1)/2/2/2,...,1,0,-1。那么只用求出2的多少次方等于N-1,再加上可能的多需要的次数2。假设2的f次方等于N-1,最大时间即为log(N-1) + 2。因此对分查找的时间复杂度为logN。再举一个实际的例子,假设最初high = 128,low = 0,则mid的最大取值为64,32,16,8,4,2,1,0,-1。大家可以计算时间。

欧几里得算法

第二个是计算最大公因数的欧几里得算法。两个整数的最大公因数Gcd是同时整除二者的最大整数。于是,Gcd(50,15) = 5。

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

算法超级简单,但是里面还是有一些精髓的。算法假设m>=n,但是如果m < n,则在第一次while循环后,m和n 会互相交换。 该算法的整个运行时间依赖于确定余数序列的长度,也就是while循环的次数。 依然举例m = 1989 和n = 1590,则余数序列是399,393,6,3,0。从而,Gcd(1989,1590) = 3。 虽然看不出余数的值是按照常数引子递减,有时候递减的非常少,例如从399递减到393。但是,我们可以证明,两次迭代以后,余数最多是原始值的一半。迭代次数至多是2logN,所以时间复杂度是logN。 怎么证明 M > N,则M mod N < M /2呢? 如果N =< M/2,则由于余数小于N,即M mod N < N <= M/2,所以余数也小于M/2。 如果N> M/2,则此时M中有个N,从而余数M-N < M/2。

幂运算

最后一个算法,是计算一个整数的幂。我们可以用乘法的次数作为运行时间的度量。 计算X的N次方常见的算法是使用N-1次乘法自乘。但是用递归算法更好。

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

如果N是偶数,则X的N次方 = X的N/2次方乘以X的N/2次方,如果N是奇数,则X的N次方 = X 的(N-1)/2 次方乘以 X的(N-1)/2次方乘以X。 显然,所需要的乘法次数最多是2logN。那么时间复杂度就是logN咯。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小狼的世界

利用JS实现的根据经纬度计算地球上两点之间的距离

第一种是默认地球是一个光滑的球面,然后计算任意两点间的距离,这个距离叫做大圆距离(The Great Circle Distance)。

15020
来自专栏木子昭的博客

机器学习三剑客之NumpyNumpy计算(重要)

NumPy是Python语言的一个扩充程序库。支持高级大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库。Numpy内部解除了Python的PI...

37460
来自专栏desperate633

LintCode 旋转字符串题目分析代码

样例 对于字符串 "abcdefg". offset=0 => "abcdefg" offset=1 => "gabcdef" offset=2 => ...

13620
来自专栏蜉蝣禅修之道

LeetCode之Jump Game II

17740
来自专栏机器学习算法与Python学习

Python: numpy总结(3)

21、dot矩阵点积 例子: ll = [[1,2,3],[4,5,6],[7,8,9]]ld = dot(ll,ll) print 'dot:',l...

34440

在Python机器学习中如何索引、切片和重塑NumPy数组

在Python中,数据几乎被普遍表示为NumPy数组。

70590
来自专栏架构之路

并查集Union-find及其在最小生成树中的应用

并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用,。 本文首先介绍并查集的定义、原理及...

37740
来自专栏前端新视界

使用 JS 输出螺旋矩阵

这是我曾经遇到过的面试题,在 LeetCode 上找到了题目的原型,难度中等。题目描述如下:

14120
来自专栏数据结构与算法

UVA - 11178 Morley's Theorem

按照刘汝佳老师说的,这道题本身没有什么算法可言, 主要是考察选手对于几何算法的应用, 我们已经知道了点A,B,C 如果要求点D的话 我们可以先求出向量C-B的坐...

363130
来自专栏大数据学习笔记

面试算法题

题目来源于牛客网:https://www.nowcoder.com/ta/coding-interviews 1、二维数组中的查找 在一个二维数组中,每一行都按...

1.3K60

扫码关注云+社区

领取腾讯云代金券