算法复杂度分析与最大子串问题算法复杂度分析最大子序列问题

算法复杂度分析

算法复杂度基本定义

算法复杂度分析基于以下四条定义:

  • 如果存在常数c与$n_{0}$使$N \geq n_{0} $时,有$T(N) \leq cf(N)$,则记 $T(N) = O(f(N))$
  • 如果存在常数c与$n_{0}$使$N \geq n_{0} $时,有$T(N) \geq cf(N)$,则记 $T(N) = \Omega(f(N))$
  • 当且仅当$T(N) = O(f(N))$且$T(N) = \Omega(f(N))$时,记$T(N) = \Theta(f(N))$
  • 若$T(N) = O(f(N))$且$T(N) \neq \Theta(f(N))$时,记$T(N) = o(f(N))$

若使用比较简单(不甚准确)的表达:

  • 当T(N)增长的比f(N)慢的时候,认为$T(N) = O(f(N))$
  • 当T(N)增长的比f(N)快的时候,认为$T(N) = \Omega(f(N))$
  • 当T(N)和f(N)一样快的时候,认为$T(N) = \Theta(f(N))$

算法复杂度分析运算

  • 加法:T1(N)=O(f(x)),T2(N)=O(g(x)),则T1(N) + T2(N) = max{O(f(x)),O(g(x))}
  • 乘法:同上假设,T1(N)* T2(N) = O(f(x) * g(x))

算法时间估算

时间估算中,认为每个操作花费时间为1,跳转,判断等所消耗时间可以忽略,例如

for(i = 0;i < N;i++) {
  for(j = 0;j < N;j++) {
    a += i+ j;
  }  
  b += i;
}

分析以上算法,内循环一次耗时N,外循环一次耗时$N * (N + 1) = N^{2} + N$,时间估算中忽略常数项和低次项,该算法花费时间$O(N^{2})$,由以上可以得出一些结论:

  • 顺序语句:时间估算为语句中耗时最多的一条
  • 判断语句:时间估算为不超过所有分支运算时间之和(与选择最耗时的一个分支相同)
  • 循环语句:时间估算为循环次数的乘积(包括嵌套循环)

最大子序列问题

问题

已知一个序列,要求求和最大的连续子序列的和。例如输入-2,11,-4,13,-5,-2,输出20(11-4+13)

求解

解法一:真.暴力求解

考虑最简单直接的解法,计算出以某个数开头的所有子序列和,取出最大的值

func solution1(data []int, num int) int {
    max_sum, this_sum := 0, 0
    for i := 0; i < num; i++ {
        for j := i; j < num; j++ {
            this_sum = 0
            for k := i; k < j; k++ {
                this_sum += data[k]
            }
            if this_sum > max_sum {
                max_sum = this_sum
            }
        }
    }
    return max_sum
} //done: 1.1903458s

解法二:改进.暴力求解

考虑以上求和的部分,每改一个j(结尾位置)都要重新计算全部子序列和。其实前面的和是被重复计算了,计算下一个子序列和时只需要加上结尾的值就可以了。

func solution2(data []int) int {
    max_sum, this_sum, num := 0, 0, len(data)
    for i := 0; i < num; i++ {
        this_sum = 0
        for j := i; j < num; j++ {
            this_sum += data[j]
            if this_sum > max_sum {
                max_sum = this_sum
            }
        }
    }
    return max_sum
} // done: 1.115286s

解法三:分治法

分治法解决这个问题的方法是:找出左侧一半的最大子串,找出右侧一半的最大子串,找出跨越左右分界的最大子串(左侧终点确定,右侧起点确定),比较得最大值。

func solution3(data []int) int {
    if len(data) == 1 {
        return data[0]
    }
    split_num := int(len(data) / 2)
    // fmt.Println(split_num)
    left_max := solution3(data[:split_num])
    right_max := solution3(data[split_num:])

    mid_left_max, mid_right_max := 0, 0
    mid_left, mid_right := 0, 0
    for i := split_num; i >= 0; i-- {
        mid_left += data[i]
        if mid_left > mid_left_max {
            mid_left_max = mid_left
        }
    }
    for i := split_num + 1; i < len(data); i++ {
        mid_right += data[i]
        if mid_right > mid_right_max {
            mid_right_max = mid_right
        }
    }
    mid_max := mid_left_max + mid_right_max
    if (mid_max > left_max) && (mid_max > right_max) {
        return mid_max
    } else if left_max > right_max {
        return left_max
    } else {
        return right_max
    }
} //done: 1.1223139s

解法四:动态规划/贪心算法

该算法原理还未理解透彻,正在研究中

func solution4(data []int) int {
    max_sum, this_sum, num := 0, 0, len(data)
    for i := 0; i < num; i++ {
        this_sum += data[i]
        if this_sum < 0 {
            this_sum = 0
        } else if this_sum > max_sum {
            max_sum = this_sum
        }
    }
    return max_sum
} //done: 1.1323284s

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

最小生成树-Prim算法和Kruskal算法

Prim算法 1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里...

57010
来自专栏图形学与OpenGL

《计算机图形学基础(OpenGL版)》勘误表

T2=[cos600∘sin600∘0−sin600∘cos600∘0001]=[−1/2−3/203/2−1/20001]T_2= \left[ \begin...

1554
来自专栏Vamei实验室

Python标准库12 数学与随机数 (math包,random包)

我们已经在Python运算中看到Python最基本的数学运算功能。此外,math包补充了更多的函数。当然,如果想要更加高级的数学功能,可以考虑选择标准库之外的n...

2418
来自专栏猿人谷

rand(),srand()产生随机数

      rand()函数可以用来产生随机数,但是这不是真真意义上的随机数,是一个伪随机数,是根据一个数,我们可以称它为种子,为基准以某个递推公式推算出来的一...

5548
来自专栏SimpleAI

Python的矩阵传播机制&amp;矩阵运算——消灭for循环!

我们知道在深度学习中经常要操作各种矩阵(matrix)。 回想一下,我们在操作数组(list)的时候,经常习惯于用for循环(for-loop)来对数组的每一个...

3563
来自专栏C语言及其他语言

【优质题解】题号1174:【计算直线的交点数】 (C语言描述)

题号1174,原题见下图: ? 解题思路: 将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多有两个交点,……,直线n 和其他n...

2966
来自专栏专知

【论文推荐】最新6篇机器翻译相关论文—词性和语义标注任务、变分递归神经机器翻译、文学语料、神经后缀预测、重构模型

【导读】专知内容组整理了最近六篇机器翻译(Machine Translation)相关文章,为大家进行介绍,欢迎查看! 1. Evaluating Layers...

4816
来自专栏小樱的经验随笔

裴蜀定理(贝祖定理)及证明

在数论中,裴蜀定理是一个关于最大公约数(或最大公约式)的定理 在数论中,裴蜀定理是一个关于最大公约数(或最大公约式)的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀...

3165
来自专栏崔庆才的专栏

自然语言处理中句子相似度计算的几种方法

在做自然语言处理的过程中,我们经常会遇到需要找出相似语句的场景,或者找出句子的近似表达,这时候我们就需要把类似的句子归到一起,这里面就涉及到句子相似度计算的问题...

4053
来自专栏JavaEdge

利用 ChiMerge 分析鸢尾花数据集基本思想实战函数说明程序运行结果参考文献

5286

扫码关注云+社区

领取腾讯云代金券