logN复杂度估算与一些示例logN复杂度估算logN复杂度算法举例

logN复杂度估算

logN复杂度的算法可以认为具有以下特性:

用常数时间将问题的大小削减为某一部分(通常是1/2)

例如分治法求最大子串问题,将一个$O(N^{2})$的问题削减为每个的1/2,每个问题复杂度为$O(N)$(有循环),所以该算法的复杂度估计为$O(NlogN)$

logN复杂度算法举例

对分查找

问题

已知一串整数按顺序排布,寻找某个指定数的下标

求解

考虑已经按顺序排列,那么使用二分查找的方法即可。对于For循环内部算法的复杂度是O(1),且每次循环都将问题缩小一半,所以认为这是一个O(logN)的算法

func binary_search(data []int, target int) int {
    left, right, mid := 0, len(data), 0
    for left != right {
        mid = int((left + right) / 2)
        // fmt.Println(mid)
        if data[mid] == target {
            return mid
        } else if data[mid] > target {
            right = mid
        } else {
            left = mid
        }
    }
    return -1
}

欧几里德算法

欧几里得算法是用于取最大公因数的算法(中国古代类似的算法好像是碾转相除法?)。这个算法中,每次循环也是将问题变得更小

func gcd(a, b int) int {
    rem := 0
    for b > 0 {
        rem = a % b
        a = b
        b = rem
    }
    return a
}

递归求幂

类似于二分查找,递归求幂的原理是$x^{2n} = x^{n} * x^{n}$相比于普通阶乘,减少了乘法的次数。同时,也是每次循环问题(N)减为原来的一半,也是一个O(logN)复杂度问题

func pow(x, n int) int {
    if n == 0 {
        return 1
    } else if n == 1 {
        return x
    } else if n%2 == 0 {
        return pow(x*x, n/2)
    } else {
        return pow(x*x, n/2) * x
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PaddlePaddle

【进阶篇】支持双层序列作为输入的Layer

导语 PaddlePaddle 高度支持灵活和高效的循环神经网络配置。本周进阶篇推文将围绕RNN模型展开,指导你如何在 PaddlePaddle 中配置和使用循...

29210
来自专栏机器学习算法工程师

经典算法题之Maximal Square

作者:叶 虎 编辑:邓高锦 Maximal Square是道非常有意思的算法题。它是一个典型的动态规划问题,同时也是2017京东面试题,2016华为机考题...

4209
来自专栏CreateAMind

keras doc 8 BatchNormalization

该层在每个batch上将前一层的激活值重新规范化,即使得其输出数据的均值接近0,其标准差接近1

2025
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (上)

一提到“A*算法”,可能很多人都有"如雷贯耳"的感觉。用最白话的语言来讲:把游戏中的某个角色放在一个网格环境中,并给定一个目标点和一些障碍物,如何让角色快速“绕...

2496
来自专栏偏前端工程师的驿站

代数几何:点,线,抛物线,圆,球,弧度和角度

一, 笛卡尔坐标系                         ? 笛卡尔坐标系是数学中的坐标系,而计算机中则采用屏幕坐标系统. ? 而三维坐标系则没有一个...

2608
来自专栏我是攻城师

十大算法,让你轻松进阶高手

4087
来自专栏数据小魔方

左手用R右手Python系列10——统计描述与列联分析

数据统计描述与列联表分析是数据分析人员需要掌握的基础核心技能,R语言与Python作为优秀的数据分析工具,在数值型数据的描述,类别型变量的交叉分析方面,提供了诸...

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

计算几何笔记

若向量$(x, y)$旋转角度为$a$,则旋转后的向量为$(xcosa - ysina, y cosa + xsina)$

2652
来自专栏wym

Huffman编码 (二叉树)

              称字符出现的次数为频数,则概率等于频数处于字符串总长;因此,频率可以用频数替代。

1372
来自专栏我和未来有约会

[Silverlight动画]转向行为 - 2D向量

转向行为已经被各种语言实现过多次了,其最底层是用向量来描述的(也是最常见的实现方式)。 概括的看,一个向量由两部分组成:一个方向和一个大小。比如,一个运动中对象...

2196

扫码关注云+社区

领取腾讯云代金券