递归方程求解

常系数线性同质递归方程

常系数线性同质递归方程.png

非同质递归方程

非同质递归方程1.png

非同质递归方程2.png

非同质递归方程2.png

Master Theorem

Master Theorem.png

堆

有n个节点的堆T，可以用一个数组H[1...n]表示。

• 根节点存储在H[1]
• T的节点x存在H[j]中，左右孩子节点在H[2j]和H[2j+1]
• H[j]的父节点如果不是根节点，则存储在H[j/2]中
  
  堆.png

堆的基本操作

DELETE.png

INSERT.png

删除和插入时间负载度均为O()

SIFT-DOWN.png

SIFT-UP.png

#include<iostream>
using namespace std;
const n 1000;
int SIFT_UP(int h[n],int i)
{
    bool done=false;
    if(i==1) return 0;
    while(i==1||done)
    {
        if(h[i]>h[i/2])
        {
            int temp=h[i];
            h[i]=h[i+1];
            h[i+1]=temp;
        }
        else{
            i/=2;
            done=true;
        }
    }
    return 0;
}
int SIFT_DOWN(int h[n],int i)
{
    bool done=false;
    if(2*i>strlen(h)) return 0;
    while(2*i>strlen(h)||done)
    {
        i=2*i;
        if(i+1<=n&&h[i+1]>h[i]) i+=1;
        if(h[i/2]<h[i])
        {
            int temp=h[i];
            h[i]=h[i/2];
            h[i/2]=h[i];
        }
        else done=true;
    }
    return 0;
}
int DELETE(int h[n],int i)
{
    int x=h[i],y=h[n];
    n-=n;
    if(i=n+1) return 0;
    h[i]=y;
    if(y>x) SIFT_UP(h,i);
    else SIFT_DOWN(h,i);
}
int DELETEMAX(int h[n])
{
    int x=h[1];
    DELETE(h,1);
    return x;
}
void MAKEHEAP(int a[n])
{
    for(int i=n/2;i>=1;i--) SIFT_DOWN(a,i);
}
void HEAPSORT(int a[n])
{
    MAKEHEAP(a);
    for(int j=n;j>=2;j--)
    {
        int temp=a[1];
        a[1]=a[j];
        a[j]=a[1];
    }
    SIFT_DOWN(a,1);
}

不相交集