复杂度高级分析技术--摊还分析
在深入浅出算法复杂度一文中，我们提到还存在一种复杂度分析策略，称为摊还分析（Amortized Analysis）。
在摊还分析中，我们主要关心某数据结构的一个操作序列中执行所有操作的平均时间，以此评价单次操作所花费的代价。摊还分析中最常用的三个技术分别是聚合分析、记账分析和势能分析。接下来我们主要讨论这三种摊还分析技术的原理以及例子。
1. 聚合分析法
1.1 原理
所谓聚合分析，就是尝试求出一个包含个操作的序列在最坏情况下花费的时间，然后将此最坏情况下每个操作的平均代价，或者说摊还代价记为。
我们考虑「二进制计数器的比特反转问题」。设有一位二进制计数器，其初值为。我们用一个长度为k的位数组count来表示这个计数器，其中count的每一位为0或1。另外我们规定，计数器值的最低位存在count[0]中，最高位存在count[k-1]中。于是，我们可以得到计数器的自增算法：
void increment(int[] count) { int i = 0; while (i < count.length && count[i]==1) count[i++] = 0 ...
Catalan数及其应用
Catalan数，即卡特兰数（英语：Catalan number），又称明安图数，是组合数学中一种常出现于各种级数问题中的数列。以比利时的数学家欧仁·查理·卡特兰的名字来命名。
它是指满足以下递推关系的数列： Catalan数的递推关系很简单，乍看之下没什么特别的，但是Catalan数却是许多计数问题的最终形式。Stanley的Enumerative Combinatorics一书中就囊括了上百个最后可以归结为Catalan数的问题，所以它的重要性不言而喻。接下来我们从上述递推关系的解开始，一步步探讨Catalan数的一些经典应用。
0. 求解Catalan数
由于Catalan数的递推关系并不是线性的，所以它的求解方法比较复杂。这里我们通过生成函数（母函数）来求解Catalan数的递推关系。
根据Catalan数的递推关系，我们设。
设函数的生成函数为： 根据递推关系，有 对上式求和，有 于是得到一个关于的二次方程： 解之即得： 考虑到牛顿二项式定理： 则可以表示为： 其中的系数为： 注意到的系数应当为正，所以 其中的系数为： 这便是卡特兰数的计算公式。
1 ...
前n项平方和怎么求？
设为前项平方和： 它的通项公式我们在中学阶段已经学习过，即 但是它的推导过程却不算简单。本文主要从组合数学的角度罗列一些此级数通项公式的推导方法。要理解本文的内容，读者应当学习过一些组合数学或离散数学的知识。
方法一：求解递推关系
考虑 上式为常系数非线性递推关系。若我们尝试直接求解，则需要先求通解，再求特解，然后将他们线性组合。显然，通解为，但是特解却并不好求。所以我们换个思路，尝试消去递推关系的非齐次项。 上述两式相减，并利用替换，可得 WOW，我们成功让等式右边的降幂了！这暗示着我们可以使用这个方法，将右边的幂函数一直降至常数。当然，随之而来的就是左边的递推关系会越变越复杂。 化简之后，我们得到了一个相当复杂的递推关系，但庆幸的是它是齐次的，我们无需再考虑通解。 我们列出上式的特征方程： 先别急着解它，我断言，它一定只有这一个实数根。否则，就将会以指数级的速度增长了，这与我们的直觉不符。当然，不难发现， 所以的的确确是它的四重根。那么该递推关系的解应该是： 注意到，根据的定义： 将前四项代入，得到一个线性方程组： 容易解得： 也就是 回顾我们的求解过 ...
LeetCode 1725. 可以形成最大正方形的矩形数目
1. 题目描述
给你一个数组rectangles，其中rectangles[i] = [li, wi]表示第i个矩形的长度为li、宽度为wi。
如果存在k同时满足k <= li和k <= wi，就可以将第i个矩形切成边长为k的正方形。例如，矩形[4,6]可以切成边长最大为4的正方形。
设maxLen为可以从矩形数组rectangles切分得到的 最大正方形 的边长。请你统计有多少个矩形能够切出边长为maxLen的正方形，并返回矩形数目。
示例 1：
输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]输出：3解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。最大正方形的边长为 5 ，可以由 3 个矩形切分得到。示例 2：
输入：rectangles = [[2,3],[3,7],[4,3],[3,7]]输出：3
提示：
1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= li, wi <= 109
li != wi
来源： ...
剑指Offer 14-I. 剪绳子
1. 题目描述
给你一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，n > 1并且m > 1），每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
来源：力扣（LeetCode）
2. 解题思路
给定一个数，假设将其拆分成个因子。根据均值不等式，当且仅当时，有最大。
考虑函数 求导得 因此，当时，单减。时，取得最大值。
所以，我们的划分因子数应当为： 以上的讨论虽然找出了极值点，但局限于连续的情形下。题目的要求是分割为整数段，我们只能求出函数的极值点，然后分别尝试极值点左右的值。
比如，当时，计算出的极值点。我们自然会依次尝试它的左右整数点和，并尽可能将均分。 ...
LeetCode 1414. 和为K的最少斐波那契数字数目
1. 题目描述
给你数字k，请你返回和为k的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
数据保证对于给定的k，一定能找到可行解。
示例 1：
输入：k = 7输出：2 解释：斐波那契数字为：1，1，2，3，5，8，13，……对于 k = 7 ，我们可以得到 2 + 5 = 7 。
示例 2：
输入：k = 10输出：2 解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。
示例 3：
输入：k = 19输出：3 解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
提示：
1 <= k <= 10^9
来源：力扣（LeetCode）
2. 解题思路
对于一个给定的数字k，注意到总是存在一个可行解的。那么在最优的方案下，它的拆分数中一定有一个最大的不超过k的Fibonacci数。
只要注意到这样一个事实，越小的数，最优方案的拆分数就越少。那么原问题就变为一个减而治之的问题。设不超过的k的最大的斐波那契 ...
剑指Offer 66. 构建乘积数组
1. 题目描述
给定一个数组A[0,1,…,n-1]，请构建一个数组B[0,1,…,n-1]，其中B[i]的值是数组A中除了下标i以外的元素的积, 即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]输出: [120,60,40,30,24]
提示：
所有元素乘积之和不会溢出32位整数 a.length <= 100000
来源：力扣（LeetCode）
2. 算法思路
乘积数组可以用一个表格表示：
A[0]
A[1]
...
A[n-2]
A[n-1]
B[0]
1
A[1]
...
A[n-2]
A[n-1]
B[1]
A[0]
1
...
A[n-2]
A[n-1]
...
...
...
...
A[n-2]
A[n-1]
B[n-2]
A[0]
A[1]
...
1
A[n-1]
B[n-1]
A[0]
A[1]
...
A[n-2]
1
其中B[i]的值是每一行的乘积。易见，我们只需分别从上三角自下而上、下三角自上而下循环乘A[i]即可。
cla ...
深入浅出算法复杂度分析
算法是计算机科学中最重要的部分，它们可以通过使用与语言和机器无关的方式进行研究。这意味着我们需要一种技术，使我们能够在不实现算法的情况下比较算法的效率。在算法分析中，两个最重要的工具是
计算的RAM模型。
最坏情况下复杂性的渐近分析。
本文将讨论算法的效率分析，以及常用的分析工具和方法。
0. Prerequisite
为了理解本文所写的内容，你需要掌握一些基本的高等数学知识。
极限的定义。
求极限的洛必达法则。
级数的定义与相关概念。
1. 算法的效率
一个算法主要有两种效率：时间效率和空间效率。时间效率，也称为时间复杂度，对应算法运行的速度。空间效率，也称为空间复杂度，是指算法根据其输入和输出所需的额外空间，或者说所需的内存单元数量。在计算机出现的早期，时间和空间等资源都是十分昂贵的。
半个多世纪依赖的技术创新使计算机的速度和内存大小提高了几个数量级。现在，算法所要求的额外空间通常不是人们关注的焦点。然而，算法时间效率重要性并不像空间那样降低。反而对于大多数问题，我们可以在时间上取得比在空间方面取得更令人满意的提升。因此，本文中，我们主要专注于算法的时间效率，当然但这里所 ...
「论文笔记」Time Series is a Special Sequence: Forecasting with Sample Convolution and Interaction.
1. 概要
论文针对的是时序预测问题（Time Series Forecasting，TSF），根据时间序列的特点创新性地提出了一个多层的神经网络框架sample convolution and interaction network（SCINet）用于时序预测。模型在多个数据集上都展示了其准确率上的优越性，且时间成本相对其他模型（如时序卷积网络TCN）也更低。本篇论文工作包含以下几点：
说明了TCN不适合解决TSF问题，尤其是其中的因果卷积对模型准确率反而有负面影响
基于时间序列的独特性提出了一个多层TSF框架SCINet，通过计算permutation entropy（PE）可以证明新的模型有更强的预测能力
构造了SCINet的基本块SCI-Block，它将输入的数据/特征下采样为两个子序列，然后使用不同的卷积滤波器提取每个子序列特征以保留不同特征的信息。同时为了减少下采样过程中信息丢失造成的影响，在每个SCI-Block中加入了两个序列间卷积特征的学习。
2. 知识梳理
2.1. 相关模型
目前用于时间序列预测的主要有三类深度神经网络：
RNNs及其变种（如LSTMs和G ...
LeetCode 3. 无重复字符的最长子串
1. 题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1：
输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2：
输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3：
输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""输出: 0
2. 算法思路
使用滑动窗口，记录下最大的窗口大小。
pos数组表示该字符上一次出现的位置，初始化为-1。
class Solution {public: int lengthOfLongestSubstring(string s) { int pos[256]; memset(pos, -1, 1024); int left = 0, right = 0, max_len = ...