读一读

算法的时间复杂度的研究,其实就是一个对一个算法随着输入规模的增大,消耗时间变化的研究。

QQ图片20171226113208.png


这是一个关于挖黄山的故事,每座黄金山都有固定需要的人手和固定的收成(不能只挖一点),在固定人数的情况下,怎样挖才能挖最多(和小偷背包装东西一样的)

class GoldM {
    public int Gold;
    public int People;

    public GoldM(int gold, int people) {
        Gold = gold;
        People = people;
    }
}

class Program
{

    static void Main(string[] args)
    {
            //五座大金山等着你
        GoldM[] goldms = new GoldM[] {
            new GoldM(3000,5),
            new GoldM(5000,6),
            new GoldM(2000,2),
            new GoldM(6000,7),
            new GoldM(2000,3)
        };
        
        Console.WriteLine(GetMoreGold(5, 10, goldms));
        Console.ReadKey();
    }

    static int GetMoreGold(int n, int w, GoldM[] goldm) {

        int[] preResult = new int[w+1];
        int[] result = new int[w+1];

        //初始化第一行(边界),i代表人数
        for (int i = 0; i <= w; i++) {
            if (i < goldm[0].People)
            {
                preResult[i] = 0;
            }
            else {
                preResult[i] = goldm[0].Gold;
            }
        }
        goldm[0].isVisited = true;
                
                //这里从1开始,因为初始化边界的时候0号金山已经被访问过了
        for (int gg = 1; gg < n; gg++) {//金矿

            for (int pp = 0; pp <= w; pp++) {//人数
                if (pp < goldm[gg].People)
                {
                    result[pp] = preResult[pp];
                }
                else {
                        //状态转移方法
                    int newGold = preResult[pp - goldm[gg].People] + goldm[gg].Gold;
                    result[pp] = Math.Max(newGold, preResult[pp]);
                }
            }
            result.CopyTo(preResult,0);//复制数组
        }

        return result[w];
    }
}


二维的动态规划,思想其实还是一样的。先划分问题,一座金山,1-n个人分别来挖的最多产量;两座金山,1-n个人分别来挖的最多产量;三座金山,1-n个人分别来挖的最多产量等。其中两座金山时,只需要关注第二座金山就可,关于第一座金山的最优解已经从第一个问题中解答出来了。同样的,第三座金山的时候,也只需要关注第三座金山(挖还是不挖),然后从第二个问题中得到前两座金山的最优解。


这是一个寻找相似东西的算法,例如根据体型颜色等我们对柚子和橙子放置了位置在笛卡尔坐标系中,横坐标表示大小,纵坐标表示颜色,这样橙子分布在左下,柚子分布在右上,此时出现一个中间的,要判断它是橙子还是柚子,我们去搜索它的附近,看看附近比较多的是橙子还是柚子,比较多的,我们就认为它就是那种水果。

特征就是大小形状等,特征的抽取,就是把这些特征转化为可以比较的数值,很重要的一步

分类就是编组,利用大数据等,事先让计算机了解到相应的特征对应的东西

回归就是预测结果,根据特征找出相似的所有的平均

应用:垃圾邮件的过滤,人脸识别,文字识别等


动态规划是一种将问题通过状态和状态转移的定义来拆分问题,每个状态都求出最优解并存储起来,通过状态转移来求下一个状态的最优解。

这是一个问题:一个人一次能上一个或两个台阶,有n个台阶,总共有多少种上法


static void Main(string[] args)
{
    Console.WriteLine(GetNum(4));
    Console.ReadKey();
}

static int GetNum(int all) {
    if (all == 0) {
        return 0;
    }

    //边界
    if (all == 1) {
        return 1;//台阶只有一个时,只有一种走法
    }

    if (all == 2) {
        return 2;//台阶有两个时有两种走法
    }

    //计算最后两个状态
    int Fi = 1;
    int Fj = 2;
    int temp = 0;

    for (int i = 2; i < all; i++) {
        temp = Fj;
        Fj = Fi + Fj;//状态转移方法
        Fi = temp;
    }

    return Fj;
}


这里的状态就是 F(n),就是表示n个台阶一共有几种上法

问题的拆分就是F(n)拆分成F(1),F(2)...F(n)

状态的转移就是:F(n) = F(n-1) + F(n-2)


贪婪算法是一个近似求解的算法,得到的结果不一定是最优的解,用来解决NP完全问题等。贪婪算法首先将问题划分成子问题,采用每一步得到最优解来估算得到一个全局最优解,这是一个近似解,怎么滴也是一个挺优秀的结果吧。衡量贪婪算法的优良,一是算法的执行速度,二是算法的计算结果和最优解的相近程度。

分治法是一个精确的算法,前提是问题的划分是均衡的,就是子问题的结果是确定的,那么得到的累计结果和原计算的结果也是一致的。两种算法都是通过划分子问题来减小问题的规模,从而更快的计算。

两种算法思想不同的是,一个得到的是最优解,不一定是最准确的结果。而分治法,是根据对问题的研究,划分子问题合成也可以变成主问题,结果是唯一的。


  1. 元素少是运行快,元素多时,速度变得非常慢

  2. 涉及“所有组合”的问题通常是NP完全问题。

  3. 不能将问题分成小问题,必须考虑各种可能情况。

  4. 如果问题涉及序列(旅行商问题)且难以解决

  5. 如果问题涉及集合(广播台集合)且难以解决


就是多项复杂程度的非确定性问题。就是需要考虑很多情况,几乎算不出来(无法通过计算出来),只能近似的得到结果(猜想出来)。

NP完全问题总的来说就是:NP=P? ,都是全靠猜


队列是一种先进先出线性的存储结构,很形象的名字就跟现实中的排队一样,我先排队自然就是我先吃饭了。队列也是一种重要的结构,广度的优先搜索等使用到了队列,还可以用队列模拟一些需要顺序访问的事件等。

1336466267_1397.jpg


就是一个先进后出的存储结构,程序类的构建,父类比子类先构造,所以父类在子类析构了之后再析构。栈的作用很大,程序的很多原理都是这个实现的,计算器的后缀表达式的计算也是需要用到栈。同时。递归程序的思想实现也是栈的模式。

timg.jpg


图的最短路径算法,啊?广度优先搜索不就是求最短路径吗?好吧,广度优先搜索是求的最短节点数到达,但是每个节点到每个节点的距离(权重)不一样,就好比东莞到惠州和东莞到北京。所以这时候就要用迪克斯特拉算法了。


class Vertex {//顶点
    public string Name;

    public Vertex(string name) {
        Name = name;
    }
}

class Edge {//边
    public Vertex From;
    public Vertex To;
    public int Weight;

    public Edge(Vertex from, Vertex to, int weight) {
        From = from;
        To = to;
        Weight = weight;
    }
}

class VisitVertex {//用来记录存在的路径和总权重,简称路径
    public int Weight;
    public bool IsVisited;
    public Vertex Vertex;

    public VisitVertex(int weight, bool isVisited,Vertex vertex) {
        Weight = weight;
        IsVisited = isVisited;
        Vertex = vertex;
    }
}

class Program
{

    static Dictionary<string, Edge[]> dict = new Dictionary<string, Edge[]>();
    static void Main(string[] args)
    {
        Vertex O = new Vertex("O");
        Vertex A = new Vertex("A");
        Vertex B = new Vertex("B");
        Vertex C = new Vertex("c");

        //构建权重图
        Edge OA = new Edge(O, A, 6);
        Edge OB = new Edge(O, B, 3);
        dict.Add("O", new Edge[] { OA, OB });
        Edge BA = new Edge(B, A, 2);
        Edge BC = new Edge(B, C, 9);
        dict.Add("B", new Edge[] { BA, BC });
        Edge AC = new Edge(A, C, 1);
        dict.Add("A", new Edge[] { AC });

        SearchLow(C);
        Console.ReadKey();
    }

    static void SearchLow(Vertex x){
        Dictionary<Vertex, Vertex> parent = new Dictionary<Vertex, Vertex>();//保存最短节点与节点的关系
        Dictionary<Vertex, VisitVertex> weight = new Dictionary<Vertex, VisitVertex>();//记录当前最小权重

        //初始化三个字典,起点开始
        //获取到起点开始指向的边
        Edge[] edges;
        dict.TryGetValue("O", out edges);
        foreach (Edge e in edges)
        {
            parent.Add(e.To, e.From);
            weight.Add(e.To, new VisitVertex(e.Weight,false,e.To));
        }


        VisitVertex go = null;
        while ((go = GetLowVertex(weight)) != null) {
            Edge[] edges2;
            dict.TryGetValue(go.Vertex.Name, out edges2);
            if (edges2 == null) break;

            foreach (Edge ee in edges2) {
                int myWeight = go.Weight + ee.Weight;
                VisitVertex orightWeight;
                weight.TryGetValue(ee.To, out orightWeight);
                if (orightWeight == null)
                {
                    //如果没有过该路径,就添加
                    weight.Add(ee.To, new VisitVertex(myWeight, false, ee.To));
                    parent.Add(ee.To, ee.From);
                }
                else {
                    if (orightWeight.Weight > myWeight)
                    {
                        //发现更短的路径,更新权重值,更改为没有访问过,修改父节点(新路径了)
                        orightWeight.Weight = myWeight;
                        orightWeight.IsVisited = false;
                        parent[ee.To] = ee.From;
                    }
                }
                    
            }
        }

           
        //输出路径和权重总值
        VisitVertex finVist;
        weight.TryGetValue(x, out finVist);
        Console.WriteLine("总权重值:" + finVist.Weight);

        Console.WriteLine(x.Name);
        Vertex cur = x;
            
        while (true) {
            Vertex aaa;
            parent.TryGetValue(cur, out aaa);
            cur = aaa;
            if (aaa == null)
            {
                break;
            }

            Console.WriteLine(aaa.Name);
        }
    }

    //获取总权重值最小,又没有被访问过路径
    static VisitVertex GetLowVertex(Dictionary<Vertex, VisitVertex> d) {
        int val = Int32.MaxValue;
        VisitVertex visit = null;
        foreach (var i in d) {
            if (i.Value.IsVisited == false) {
                if (i.Value.Weight < val) {//新路径比旧路径权重值小
                    val = i.Value.Weight;
                    visit = i.Value;
                }
            }
        }

        if (visit != null) {
            //标志该路径以被访问过
            visit.IsVisited = true;
        }
        return visit;
    }
}


这种算法也有限制,就是图中不能出现环图,也不能出现负权重。

详情看:吃菜网-迪克斯特拉算法