分类：算法

已知先序及中序遍历，重建二叉树

package cn.pbdata.util;

public class PreMidToAfter {

    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(){
            left = null;
            right = null;
        }
    }
    
    public TreeNode rebuild(int[] pre,int[] mid){
        return rebuild(pre,0,pre.length-1,mid,0,mid.length-1);
    }
    
    public TreeNode rebuild(int[] pre,int ps,int pe,int[] mid,int ms,int me){
        if(pre == null || pre.length == 0 || mid == null || mid.length==0){
            return null;
        }
        if(ps > pe){
            return null;
        }
        int val = pre[ps];
        TreeNode root = new TreeNode();
        root.val = val;
        
        int index;
        for(index = ms ; index <= me;index++){
            if(val == mid[index]){
                break;
            }
        }
        
        int leftPreStart = ps + 1;
        int leftPreEnd = ps + index - ms;
        int leftMidStart = ms;
        int leftMidEnd = index - 1;
        
        root.left = rebuild(pre,leftPreStart,leftPreEnd,mid,leftMidStart,leftMidEnd);
        
        int rightPreStart = ps + index -ms + 1;
        int rightPreEnd  = pe;
        int rightMidStart = index + 1;
        int rightMidEnd = me;
        root.right = rebuild(pre,rightPreStart,rightPreEnd,mid,rightMidStart,rightMidEnd);
        return root;
    }
    public void preView(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val);
        preView(root.left);
        preView(root.right);
    }
    public void midView(TreeNode root){
        if(root == null){
            return;
        }
        midView(root.left);
        System.out.print(root.val);
        midView(root.right);
    }
    public void lastView(TreeNode root){
        if(root == null){
            return;
        }
        lastView(root.left);
        lastView(root.right);
        System.out.print(root.val);
    }
    
    
    public static void main(String[] args){
        PreMidToAfter pt = new PreMidToAfter();
        int[] pre = { 1, 2, 4,7,3,5,6,8};
        int[] mid = {4,7,2,1,5,3,8,6};
        TreeNode node1 = pt.rebuild(pre, mid);
        pt.preView(node1); 
        System.out.println("");
        pt.midView(node1);
        System.out.println("");
        pt.lastView(node1);
        System.out.println("");
        
    }
}

2015年12月2日

算法运行时间-logN、NlogN

算法的运行时间通常与下列函数成比例：

1	大部分程序的大部分指令之执行一次，或者最多几次。如果一个程序的所有指令都具有这样的性质，我们说这个程序的执行时间是常数。
logN	如果一个程序的运行时间是对数级的，则随着N的增大程序会渐渐慢下来，如果一个程序将一个大的问题分解成一系列更小的问题，每一步都将问题的规模缩减成几分之一，一般就会出现这样的运行时间函数。在我们所关心的范围内，可以认为运行时间小于一个大的常数。对数的基数会影响这个常数，但改变不会太大：当N=1000时，如果基数是10，logN等于3；如果基数是2，logN约等于10.当N=1 00 000，logN只是前值的两倍。当N时原来的两倍，logN只增长了一个常数因子：仅当从N增长到N平方时，logN才会增长到原来的两倍。
N	如果程序的运行时间的线性的，很可能是这样的情况：对每个输入的元素都做了少量的处理。当N=1 000 000时，运行时间大概也就是这个数值；当N增长到原来的两倍时，运行时间大概也增长到原来的两倍。如果一个算法必须处理N个输入（或者产生N个输出），那么这种情况是最优的。
NlogN	如果某个算法将问题分解成更小的子问题，独立地解决各个子问题，最后将结果综合起来，运行时间一般就是NlogN。我们找不到一个更好的形容，就暂且将这样的算法运行时间叫做NlogN。当N=1 000 000时，NlogN大约是20 000 000。当N增长到原来的两倍，运行时间超过原来的两倍，但超过不是太多。
N平方	如果一个算法的运行时间是二次的（quadratic），那么它一般只能用于一些规模较小的问题。这样的运行时间通常存在于需要处理每一对输入数据项的算法（在程序中很可能表现为一个嵌套循环）中，当N=1000时，运行时间是1 000 000；如果N增长到原来的两倍，则运行时间将增长到原来的四倍。
N三次方	类似的，如果一个算法需要处理输入数据想的三元组（很可能表现为三重嵌套循环），其运行时间一般就是三次的，只能用于一些规模较小的问题。当N=100时，运行时间就是1 000 000；如果N增长到原来的两倍，运行时间将会增长到原来的八倍。
2的N次方	如果一个算法的运行时间是指数级的（exponential），一般它很难在实践中使用，即使这样的算法通常是对问题的直接求解。当N=20时，运行时间是1 000 000；如果增长到原来的两倍时，运行时间将是原时间的平方！

log log N 可以看作是一个常数：即使N很多，两次去对数之后也会变得很小

转自：http://clarkluo2004.blog.163.com/blog/static/32973801200845115213422/

2015年11月25日

分类： 算法

已知先序及中序遍历，重建二叉树

算法运行时间-logN、NlogN

分类：算法