《算法问题实战策略》-chaper17-部分和

时间:2022-02-23 00:15:39

数组上的一个基本优化——部分和:

对于一定长度的数组,我们想不断访问这个数组上的某个区间的和,我们能够怎么做呢?这里先不去谈一些数据结构在这个问题上的优化处理。首先我们最简单的一个方法就是穷举出所有区间段然后求值保存起来,但是O(n^2)的时间复杂度并没有太多的实际应用的意义。

这里考虑一个非常简单但是常用的优化方法——部分和。

对于一个数组a[],我们在输入数据的时候,顺便记录数组部分和psum[],而对于部分和数组psum[]的定义如下:

psum[i] = ∑a[j] , j∈[1,j].

基于部分和数组,能够看到,我们在多次访问数组某个区段的和的时候,可以通过O(1)的时间复杂度得到,即a[i] + a[i+1]+…a[j] = psum[j] – psum[i].

结合一个具体的题目我们来尝试一下这个方法:

Q:假设有以正数和负数组成的数组A[],其数组中区间之和最接近0的区间。

考虑从部分和的角度去优化处理这个问题,我们首先得到这个数组的部分和,但是这里需要用结构体记录一下psum[]当前的下标。然后我们回到一开始的问题,区兼职和最接近零,也就是min{|psum[i]-psum[j]| |  i、j∈[1,n]},我们将psum[]数组进行排序,然后在线性时间复杂度O(n)下维护一个psum[i+1]-psum[i]的最小值即可,两个结构体元素存着的下标变量即是原来数组对应的区段。

综合起来,整体的时间复杂度是O(nlog n) + O(n),相比O(n^2)已经优化很多了。

在c++STL中有直接进行部分和的函数,简单的用法如下:

  #include <iostream>

 #include <functional>

 #include <numeric>

 using namespace std;

int main () {

   int val[] = {,,,,};

   int result[];

   partial_sum (val, val + , result);//用法:partial_sum(<数组起点>,<数组终点>,记录部分和的数组)

   cout << "using default partial_sum: ";

   for (int i=; i < ; i++)

        cout << result[i] << ' ';

  return ;

 }

《算法问题实战策略》-chaper17-部分和的更多相关文章

  1. 算法问题实战策略 PICNIC

    下面是另一道搜索题目的解答过程题目是<算法问题实战策略>中的一题oj地址是韩国网站 连接比较慢 https://algospot.com/judge/problem/read/PICNIC ...

  2. 《算法问题实战策略》-chaper7-穷举法

    关于这一章节<算法实战策略>有一段概述问题,我认为对于编程人员来说非常有价值,故在这里进行如下的摘抄: 构想算法是很艰难的工作.相比大家都经历过,面对复杂的要求只是傻乎乎地盯着显示器,或者 ...

  3. 《算法问题实战策略》-chaper32-网络流

    基本的网络流模型: 在图论这一块初步的应用领域中,两个最常见的关注点,其一时图中的路径长度,也就是我们常说的的最短路径问题,另一个则是所谓的“流问题”. 流问题的基本概念: 首先给出一张图. 其实所谓 ...

  4. 《算法问题实战策略》-chaper13-数值分析

    这一章节主要介绍我们在进行数值分析常用的二分.三分和一个近似求解区间积分的辛普森法. 首先介绍二分. 其实二分的思想很好理解并且笔者在之前的一些文章中也有所渗透,对于二次函数甚至单元高次函数的零点求解 ...

  5. 《算法问题实战策略》——chaper9——动态规划法技巧

    Q1: 数字游戏: 两个人(A.B)用n个整数排成的一排棋盘玩游戏,游戏从A开始,每个人有如下操作: (1)    拿走棋盘最右侧或者最左侧的棋子,被拿走的数字从棋盘中抹掉. (2)    棋盘中还剩 ...

  6. 《算法问题实战策略》-chaper8-动态规划法

    Q1:偶尔在电视上看到一些被称为“神童”的孩子们背诵小数点以后几万位的圆周率.背诵这么长的数字,可利用分割数字的方法.我们用这种方法将数字按照位数不等的大小分割后再背诵. 分割形式如下: 所有数字都相 ...

  7. 《算法问题实战策略》-chaper21-树的实现和遍历

    这一章节开始介绍一个数据结构中的一个基本概念——树. 我们从数据结构的解读来解释树结构的重要性,现实世界的数据除了最基本的线性结构(我们常用队列.数组和链表等结构表征),还有一个重要的特性——层级结构 ...

  8. 算法问题实战策略 QUADTREE

    地址 https://algospot.com/judge/problem/read/QUADTREE 将压缩字符串还原后翻转再次压缩的朴素做法 在数据量庞大的情况下是不可取的 所以需要在压缩的情况下 ...

  9. 算法问题实战策略 DICTIONARY

    地址 https://algospot.com/judge/problem/read/DICTIONARY 解法 构造一个26字母的有向图 判断无回路后 就可以输出判断出来的字符序了 比较各个字母的先 ...

随机推荐

  1. &lbrack;NOIP2015&rsqb;信息传递

    [NOIP2015]信息传递[问题描述]有

  2. JS备忘录

    /** *删除数组指定下标或指定对象 */ Array.prototype.remove = function (obj) { for (var i = 0; i < this.length; ...

  3. ligerui grid行编辑示例

    <%@ page contentType="text/html; charset=UTF-8" %> <% String path = request.getCo ...

  4. 在安装ISE的情况下,充分利用ISE的安装目录,查找资料

    2013-06-22 11:03:02 在找资料时,通过官网输入关键字的方法找资料,有事会给出很多版本的链接.或者找不到,下面给出一种简便的方法,可以快速找到想要的资料. 如果要找ISE各个工具如pl ...

  5. 8&period;6中关于PSNR&lpar;峰值信噪比&rpar;&comma; img-&gt&semi;quad的解释

    在JM代码中,多次遇到img->quad这个东西,而在官方代码中只给出了一句说明: 我开始看了好几遍都没有看懂,然后看到后面有snr,所以想应该和snr有关吧. 然后再代码中寻找snr,发现jm ...

  6. linux LVM 逻辑卷

    fdisk pvcreate vgcreate lvcreate 查看显示 创建 删除 扩容 激活 扫描查找 LV lvdisplay lvcreate lvremove lvextend lvcha ...

  7. Angular开发者指南(一)入门介绍

    什么是Angular AngularJS是动态Web应用程序的结构框架. 它允许您使用HTML作为模板语言,并允许您扩展HTML的语法以清晰,简洁地表达应用程序的组件.AngularJS的数据绑定和依 ...

  8. java设置字符串编码、转码

    Unicode(统一码.万国码.单一码)是计算机科学领域里的一项业界标准,包括字符集.编码方案等.Unicode 是为了解决传统的字符编码方案的局限而产生的,它为每种语言中的每个字符设定了统一并且唯一 ...

  9. bzoj1625 &lbrack;Usaco2007 Dec&rsqb;宝石手镯

    01背包 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring& ...

  10. Intro to Python for Data Science Learning 4 - Methods

    Methods From:https://campus.datacamp.com/courses/intro-to-python-for-data-science/chapter-3-function ...