精华内容
下载资源
问答
  • 主定理常用于计算递推式的时间复杂度。 转自:https://www.cnblogs.com/jdflyfly/p/3954637.html

    主定理常用于计算递推式的时间复杂度。

    转自:https://www.cnblogs.com/jdflyfly/p/3954637.html

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 1的时候很明显发现会有一个关系式,但是实际上我们在做运算的时候,如果一步一步的按照递推式计算,将会消耗大量的时间(最短也是O(n)的时间复杂度),于是我们这个时候就需要引入矩阵乘法和快速幂来减少时间复杂度 ...

    斐波那契数列
    f(0)=0; f(1)=1; f(n)=f(n-1)+f(n-2),n>1

    从上面这个方程中我们可以看到很明显的递推关系,当n>1的时候很明显发现会有一个关系式,但是实际上我们在做运算的时候,如果一步一步的按照递推式计算,将会消耗大量的时间(最短也是O(n)的时间复杂度),于是我们这个时候就需要引入矩阵乘法和快速幂来减少时间复杂度

    矩阵乘法:
    设A为mp的矩阵,B为pn的矩阵,那么称m*n的矩阵C为矩阵A与B的乘积,其中矩阵C中的第i行第j列元素可以表示为A的第i行与B的第j列对应元素乘积和

    矩阵相乘:矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数(column)和第二个矩阵的行数(row)相同时才有意义。一般单指矩阵乘积时,指的便是一般矩阵乘积。一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。由于它把许多数据紧凑的集中到了一起,所以有时候可以简便地表示一些复杂的模型。
    设A为mp的矩阵,B为pn的矩阵,那么称m*n的矩阵C为矩阵A与B的乘积,记作C=AB:

    首先:快速幂取模模板
    例如:求x的n次幂并取模

    	int quickmod(long long n,long long x,long long r) //整型的
    	{
    		int ans=1;
    		while(n)
    		{
    			if(n&1)
    				ans=ans*x%r;
    			n>>=1;
    			x=x*x%r;
    		}
    		return ans;
    	} 
    

    矩阵 (struct)来定义

    struct   Matrix{
    	int m[2][2];
    } 
    

    矩阵的乘法运算

        Matrix mul(Matrix k,Matrix n)
        {
            matrix ans;
            for(int i=0;i<2;i++)
                for(int j=0;j<2;j++)
                {
                    ans.m[i][j]=0;
                    for(int k=0;k<2;k++)
                    //ans.m[i][j]+=A.m[i][k]*B.m[k][j]%mod;
            		//修正
            		ans.m[i][j] +=A.m[i][k]*B.m[k][k];
            		ans.m[i][j] = ams.m[i][j]%mod;
                }
            return ans;
        }
    

    两者结合一下即可
    最终代码

    #include <iostream>
    using namespace std;
    const long long mod=1e9+7;
    struct  Matrix{
    	int m[2][2];
    };
    Matrix mul(Matrix A,Matrix B)
    {
        Matrix ans;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
            {
                ans.m[i][j]=0;
                for(int k=0;k<2;k++)
                    //ans.m[i][j]+=A.m[i][k]*B.m[k][j]%mod;
            		//修正
            		ans.m[i][j] +=A.m[i][k]*B.m[k][k];
            		ans.m[i][j] = ams.m[i][j]%mod;
            }
        return ans;
    }
    Matrix quickmod(long long n,Matrix x)
    {
    	Matrix ans;
    	ans.m[0][0]=1;
    	ans.m[0][1]=0;
    	ans.m[1][0]=0;
    	ans.m[1][1]=1;
    	while(n)
    	{
    		if(n&1)
    			ans=mul(ans,x);
    		n>>=1;
    		x=mul(x,x);
    	}
    	return ans;
    }
    int main()
    {
    	 Matrix A,ans;
    	 int n;
    	 cin>>n;
    	 ans.m[0][0]=1;
    	 ans.m[0][1]=0;
      	 A.m[0][0]=1;
     	 A.m[0][1]=1;
    	 A.m[1][0]=1;
    	 A.m[1][1]=0;
    	 ans=mul(ans,quickmod(n-1,A));
    	 cout<<ans.m[0][0]<<endl;
    	 return 0;
    }
    
    

    然后如何将线性递推式转化成矩阵的形式来求解呢
    先看一道hdu的题A Simple Math Problem hdu 1757

    Problem Description
    Lele now is thinking about a simple function f(x).
    If x < 10 f(x) = x.
    If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
    And ai(0<=i<=9) can only be 0 or 1 .
    Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
    Input
    The problem contains mutiple test cases.Please process to the end of file.
    In each case, there will be two lines.
    In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
    In the second line , there are ten integers represent a0 ~ a9.
    Output
    For each case, output f(k) % m in one line.
    Sample Input
    10 9999
    1 1 1 1 1 1 1 1 1 1
    20 500
    1 0 1 0 1 0 1 0 1 0
    Sample Output
    45
    104

    这里 当x<10的时候 f(x) = x;
    当x>=10的时候 f(x)=a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)这也就是一个线性递推式了
    我们就可以把他变成矩阵的形式来求解。

    #include <iostream>
    #include <cstring>
    using namespace std;
    typedef long long ll;
    const int MAX =10; //最多也就一个10*10的矩阵乘法
    struct matrix
    {
        ll m[MAX][MAX];
    };
    matrix mul(matrix A,matrix B,ll mo)
    {
        matrix ans;
        for(int i=0;i<MAX;i++){
            for(int j=0;j<MAX;j++){
                ans.m[i][j] = 0;
                for(int k=0;k<MAX;k++){
                    ans.m[i][j] += A.m[i][k]*B.m[k][j];
                    ans.m[i][j] = ans.m[i][j]%mo;
                }
            }
        }
        return ans;
    }
    matrix quickmod(matrix A,ll k,ll mo)
    {
        matrix ans;
        memset(ans.m,0,sizeof(ans.m));
        for(int i=0;i<MAX;i++){
            ans.m[i][i] = 1;
        }
        while(k){
            if(k&1)
                ans = mul(ans,A,mo);
            k>>=1;
            A = mul(A,A,mo);
        }
        return ans;
    }
    int main()
    {
        ll k,m;
        matrix Init;
        for(int i=0;i<MAX;i++){
            Init.m[i][0] = MAX-i-1;
        }
        while(cin>>k>>m){
            matrix T;
            if(k<10){
                cout<<k<<endl;
                continue;
            }
            memset(T.m,0,sizeof(T));
            for(int i=0;i<MAX;i++){cin>>T.m[0][i];} //记录下a0,a1,a2,a3,a4……
            for(int i=1;i<MAX;i++){ // 初始化后面的根据矩阵
                T.m[i][i-1] = 1;
            }
    
            cout << mul(quickmod(T,k-9,m),Init,m).m[0][0] <<endl;
        }
    
        return 0;
    }
    
    展开全文
  • 积分做和渐进的界 递推方程与算法分析 递推方程:an与某些ai联系起来(i<n) 实例:斐波那契数列、hanoi塔问题、插入排序 迭代法 与递推法不同:第n项只与第n-1项有关 例:Hanoi 换元迭代 ...

    序列求和的方法

    一、数列的求和公式

    等差、等比、调和级数。

    拓展:放缩法(放大法求上界)  例子:二分检索

               积分做和式渐进的界

     

    递推方程与算法分析

    递推方程:an与某些ai联系起来(i<n)

    实例:斐波那契数列、hanoi塔问题、插入排序

     

    迭代法

    与递推法不同:第n项只与第n-1项有关

    例:Hanoi

    换元迭代

     

    将分数问题转化成整数问题解决,简化计算。

     

    差消法化简高阶递推方程

    an与前面连续很多项有关(最典型的是与前面n-1项都有关)通过差消法转化为迭代法解决。

    例:快速排序

    最终迭代求解

     

    递归树

    递归树就是在每个结点位置放上合并子问题的规模,叶子结点放上其子问题的一棵树。

    主定理

    主定理是解决一类多项式形式的规模不断缩小的问题的直接给出复杂度的方法。

    不能使用主定理的例子

    常见的两类递推方程

    解决:差消化简法、递归树

    解决:主定理

     

     

     

    展开全文
  • 计算时间复杂度(分治法与递归) ...1.递推求解法 我们上面的求解方式都是递推求解,写出其递推式,最后求出结果。 例如:合并排序算法的时间复杂度递推求解: 2.递归树求解法 递归树求解方式其实...

    计算时间复杂度(分治法与递归)

    本文为转载,原链接忘记了
    分治法的道理非常简单,就是把一个大的复杂的问题分为a(a>1)个形式相同的子问题,这些子问题的规模为n/b,如果分解或者合并的复杂度为f(n),那么总的时间复杂度可以表示为:
    在这里插入图片描述

    1.递推求解法 我们上面的求解方式都是递推求解,写出其递推式,最后求出结果。 例如:合并排序算法的时间复杂度递推求解:
    在这里插入图片描述

    2.递归树求解法 递归树求解方式其实和递推求解一样,只是递归树更清楚直观的显示出来,更能够形象的表达每层分解的结点和每层产生的成本有多少。例如:
    在这里插入图片描述

    在这里插入图片描述

    3.大师解法
    在这里插入图片描述

    递归树
    在这里插入图片描述

    时间复杂度=叶子数*T(1)+成本和
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    例子:
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    首先从递归树中观察每层产生的成本发展趋势,每层的成本有时不是那么有规律,需要仔细验证才行。比如我们得到第3层是(5/16)2n2,需要验证第4层是(5/16)3n2,…。经过验证,我们发现每层成本是一个等比数列,公比为5/16<1,呈递减趋势,那么只需要计算第一项即可。时间复杂度:T(n)=O(n2)

    展开全文
  • 前两天校园招聘的笔试,发现趋势科技和微软都考了根据递推式计算时间复杂度的题目,例如:已知某程序的时间复杂度的递推公式为:T(n)=25T(n/5)+n^2,求T(n)? 先转网上的主定理, 对照主定理,题中a=25,b=5,f...
  • 将支持向量集设定为作用集,迭代地局部优化作用集以获得全局最优解,并引进递推式算法降低计算复杂度。不同于序贯最小优化(SMO)收敛目标函数的思路,该算法寻找支持向量在最优状态下的分布,对Karush-Kuhn-Tucker(KKT)...
  • 递归算法时间复杂度计算方程一个递归方程:    在引入递归树之前可以考虑一个例子:  T(n) = 2T(n/2) + n2  迭代2次可以得:  T(n) = n2 + 2(2T(n/4) + (n/2) 2)  还可以继续迭代,将其完全展开可得...
  • 但是巧妙的将递推式计算转换成矩阵的幂运算之后,可以利用分治法高效的求幂运算,从而将O(n)转换成了O(log(n))的时间复杂度。证明题目已经给出,我们需要做的仅仅是将矩阵的幂运算代码实现。  我用了运算符重载...
  • 主定理 符号Θ ,既是上界也是下界,等于。 符号O ,表示上界,时间复杂度小于等于该...假设我们有递推关系: T(n)=aT(n/b)+f(n) T(n)=aT(n/b)+f(n) T(n)=aT(n/b)+f(n) 其中,n 为问题的规模,a 为递推下子...
  • 首先了解线性递推数列的特征方程 (1)数列的特征方程: 假设一个数列:Xn+2 = C1Xn+1 + C2Xn 设有r,s使Xn+2 - rXn+1 = S(Xn+2-rXn); 所以Xn+2 = (s+r)Xn+1 - srXn; 得到 C1 = s+r;C2 = -sr; 消去s得到特征...
  • 特征方程法解一阶线性代数递推式 数列{ana_nan​}满足a1=b,an+1=can+da_1=b,a_{n+1}=ca_n+da1​=b,an+1​=can​+d,求该数列的通项公式 针对递推关系式作出一个特征方程x=cx+dx=cx+dx=cx+d 定理:设上述递推...
  • 算法复杂度计算 方法一 代换法  —局部代换  这里直接对n变量进行代换  —替换成对数或者指数的情形 n = 2^m  —整体代换  这里直接对递推项进行代换  —替换成内部递推下标的形式 T(2^n) = S(n) ...
  • 针对空间连接系统, 提出一种分布式递推状态估计算法, 并给出算法收敛的充分必要条件.... 与集总Kalman 滤波相比, 在牺牲少量估计精度的情况下, 所提出算法大幅降低了计算复杂度和数据传输压力.</p>
  • 在递归与分治的算法复杂度分析时,通常可得到一个递推公式,形如: 其中为问题的规模,为递归的子问题的数量,为子问题的规模,为每次递归带来的额外计算的函数。要计算这个子,有以下三种情形: 当,,则 当...
  • 前言 这是我为了方便明天考试之前复习放的博客,没有任何学习价值。...对于归并排序,其运行时间的递推式为 : T(n)=2T(n/2)+O(n); (2T(n/2)是左右两边都要归并的时间,O(n)是合并有序表的时间) 可得 :a=2 ,
  • 约瑟夫环问题问题:n个人编号1~n,报数报到m的出队,问最后一个人是谁(队列成环)数学递推:复杂度O(n) 优化: 取模运算是算术操作中中最慢的(在当前的计算机硬件中基本...通常在递推式中有取模操作的课转化为加减法
  • 考研小助手-mathematica求解递推方程

    千次阅读 2015-04-18 12:52:15
    mathematica求解递推方程分析程序复杂度时经常要用到递推式,采用mathematica可以验证计算结果。问题求T(n)T(n)表达式,已知T(1)=0T(1)=0 T(n)=T(n−1)+n−1T(n)=T(n-1)+n-1代码RSolve[{T[n] == T[n - 1] + n - 1, ...
  • 而在计算分治法的算法复杂性时,我们往往能得到这样一个关于复杂性公式T(n)的递推式: 其中, n为数据规模, k为分治后子规模运算的数量, m为规模的划分数,一般为二分,即m=2。 f(n)为分治后需要进行的额外...
  • 总结一下吧。。 像这种题,输入很简单,就几个数,...如果手算的话,心细一点可能就会发现递推关系了,化简一下关系就会变得很简单。没发现的话就把数列写出来,然后加减乘除看看相邻项有没有什么联系啊。。。再不
  • 50%:递推计算。设F[n]表示n个人时最后剩下的人的编号。每 增 加 m-1 个 人 , 答 案 向 后 移 动 m 位 。 于 是 递 推 为 F[n]=F[n-m+1]%(n-m+1)+m,初始F[1]=1。时间复杂度O(nm)O({n\over m})。 100%:容(da...
  • 矩阵乘法优化递归

    2017-05-24 22:31:18
    序:在OI比赛中,很多情况下我们可以能通过打表(找规律)或者某些方式发现一个递归式。 例如:f(n) = f(n - 1)+f(n - 2),(斐波那契...如果不学习矩阵乘法优化的话,我们恐怕永远不会想到计算递推式还可以进行优化。
  • 预处理组合数+组合递推式2. 预处理阶乘+逆元3. 卢卡斯定理4. 高精度组合数 0. 前言 组合数求解有很多种方式,不同的方式对应这不同的时间复杂度,难以程度也是不尽相同。根据数据范围选择对应的方法即可。 1. ...
  • O(lgn)计算斐波那契数

    2013-05-13 22:18:29
    2.常规的求斐波那契数时间复杂度为O(n),直接用递推式求 f[0]=f[1]=0; for(i=2;i;i++) f[i]=f[i-1]+f[i-2]; 或者先求出通项公式,特征值为x1,x2,则 f(n)=A*x1^n+B*x2^n 3.现在主要讨论O(lgn)
  • 组合数的计算方式

    2021-06-11 15:20:17
    一般是通过这种递推式处理: Cij=Ci−1j+Ci−1j−1C_i^j = C_{i-1}^j+C_{i-1}^{j-1}Cij​=Ci−1j​+Ci−1j−1​ 2.阶乘逆元   适用于时间复杂度O(N)O(N)O(N),且模数为质数的情况. 因为 Cab=a!b!(a−b)!C_a^b = \...
  • 一.题目: 已知F[n]=F[n-1]+F[n-2],F[1]...给出的递推式可以看做状态转移矩阵,可以表示为: 那么F[n]和F[0],F[1]的关系可以表示为 如何暴力求解转移矩阵的n-1方,求矩阵的次数为n-2次,每次两两矩阵相乘的复...
  • 算法复习总结

    2019-11-26 01:04:03
    算法复习总结结构化程序设计算法三要素常用的时间复杂度关系枚举、递推算法的实施步骤枚举递推无障碍交通网络的递推关系算法有限判断条件可能遇到的代码如下: 结构化程序设计 自定向下 模块化设计 结构化编码 ...
  •  这里大概给出最简单的几种方法:扰动法(化为递推式),斯特林数(离散微积分),高阶差分(牛顿级数),伯努利数(指数生成函数)…  不同方法的思维难度、普适程度、实现难度、时间复杂度上面都有差异…同时自然数幂...
  • 针对二元探测传感器网络目标定位与跟踪问题,提出一种递推的质心定位方法,推导出...算法不需要先验统计信息以及序贯的处理方式等因素,降低了算法的计算复杂度。仿真结果验证了递推公式的正确性和跟踪算法的有效性。
  • 主定理常用于计算递推式的时间复杂度。 转载于:https://www.cnblogs.com/jdflyfly/p/3954637.html

空空如也

空空如也

1 2 3 4 5
收藏数 85
精华内容 34
关键字:

计算复杂度递推式