数据结构与算法

源代码地址：GitHub - firstsaofan/Data-structure-and-algorithm at develop

二分法

例子：经典场景 猜数字游戏

1-100我心里指定一个数字，你来猜这个数字，

1.可以1------100一个一个猜

2.你可以直接从50 来猜 然后 25 13 7 4 2 1

代码

//二分查找 查找次数O(logn) 
//猜数字游戏  
Console.WriteLine("输入一个数字，代表1----N的范围");
var n = Console.ReadLine();
//输入的数字字符转化成整型
var max = StringToNum(n);
int start = 0;
int end = max - 1;
//电脑随机在1---n之间生成一个随机数，让用户猜
Random ran = new Random();
var item = ran.Next(1, max);
Console.WriteLine(@$"输入1-----{max}之间的您猜的整数");
int count = 0;
while (start <= end)
{
    //元素中间索引

    var mid = (start + end) / 2;//这个是自动向下取整的
    
    Console.WriteLine(@$"自动猜测的数字是{mid}");
    count++;
    if (mid == item)
    {
        Console.WriteLine("恭喜您，猜对了！！！");
        Console.WriteLine("游戏结束！！！");
        Console.WriteLine(@$"一共猜了{count}次");
        break;
    }
    else if (mid < item)
    {
        Console.WriteLine("数字猜小了！！！");
        //猜的数字小了 ，则正确的数字应该在右边  ---------------mid----------------
        //左边的所有元素全部排除则
        start = mid + 1;
    }
    else if (mid > item)
    {
        Console.WriteLine("数字猜大了！！！");
        //猜的数字小了 ，则正确的数字应该在左边  ---------------mid----------------
        //右边的所有元素全部排除则
        end = mid - 1;
    }
 
}

//Console.WriteLine("Hello, World!");

 static int StringToNum(string n)
{
    return Convert.ToInt32(n); ;
}
注意

注意事项为start，end，mid是索引而不是对应的数，由于猜数字游戏这个案例容易混淆索引和数值，需要注意。

总结

二分法的时间复杂度：log2n{log_2{n}} 2可以省略

常见的几种大O运行时间。

下面从快到慢的顺序列出了你经常会遇到的5种大O运行时间

1.O(logn)O({log{n}})，也叫对数时间，这样的算法包括二分查找。

2.O(n), 也叫线性时间，这样的算法包括简单查找。

3.O(n*logn{log{n}})，这样的算法包括快速排序----------一种速度较快的排序算法

4.O(n2)({n^2}),这样的算法包括选择排序-------------一种速度较慢的排序算法

5.O(n!),这样的算法包括旅行商问题的解决方案---------------一种非常慢的排序算法

Tips

旅行商问题(TravelingSalesmanProblem，TSP)是一个经典的组合优化问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。

选择排序法

//Tips
/*
 * pop()方法是python的一个内置方法，可以通过列表、数组、字典、集合等的实例对象去调用。
 * 不加参数则是删除最后一个
 * arr.pop(2) 是删除索引2的元素并返回元素2的值
 * 也就是返回第三个元素的值 并删除它 形成一个新的数组
 */

//选择排序法
//eg:例如音乐app 你喜欢的歌曲歌单 里面的喜爱程度 是根据每首歌的播放次数来倒序排序的
/***
 * 歌曲          播放次数  
 * a                10
 * b                9
 * c                8
 * d                7
 * e                6
 **/
//每一次播放都会影响 需要找出最大的在第一个
var list =new List<int>() {1,10,9,88,8,7,6,22 };
var sortList = SelectSort(list);
foreach (var item in sortList)
{
    Console.Write(item+",");
}
Console.WriteLine();

static List<int> SelectSort(List<int> list) 
{
    var listSort = new List<int>();
    //如果一开始不定下来 后面取动态的list.count会少（当循环的i次数等于list.count时候，后面的list直接丢失）
    //结果如下：88,22,10,9
    //正确 88,22,10,9,8,7,6,1,
    var maxleng = list.Count;
    for (int i = 0; i < maxleng; i++) {
        //找出这个list里面最大的元素
        var max = FindMax(list);
        //移除这个元素 然后继续去新的list去找最大的元素最终形成一个有序的从大到小的list
        listSort.Add(list[max]);
        list.RemoveAt(max);

    }
    //返回有序集合
    return listSort;
}

static int FindMax(List<int> list)
{
    int max = list[0];
    int maxIndex = 0;
    for (int i = 0; i < list.Count; i++)
    {
        if (max < list[i])
        {
            max = list[i];
            maxIndex = i;

        }
    }
    return maxIndex;
}

Console.WriteLine("Hello, World!");
总结：

时间复杂度

选择排序是一种灵巧的算法，但其速度不是很快。快速排序是一种更快的排序算法，其运行时间为O(n*logn{log{n}})，这将在后面学习。

疑惑：

需要检查的元素越来越少？

​ 随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素只有一个。既然如此，运行时间怎么还是O(n2{n^2})呢？这个问题问得好,这与大O表示法中的常数相关。后面将在第四章详细学习，这里只是简单说一说。（本人手敲单纯只是想加深一遍印象而已）

​ 你说的没错，并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素数依次为n-1，n-2，

n-3，…… 2，1。平均每次检查的元素数为O$$(\frac{1}{2}(n+1))$$,因此运行时间为O$$(n\frac{1}{2}(n+1))$$。但大O表示法省略如$$\frac{1}{2}$$这样的常数，因此简单写作O(n x n) 或者 O(n2n^2)。

递归

//Recursion 递归算法
/* 
 * 编写递归函数时，必须告诉它合适停止递归。正因为如此，每个递归函数都有两部分，基线条件（base case）和递归条件（recursion case）。
 * 递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免无限循环。从下面Recursion方法中可以看到对应的基线条件和递归条件
 */

//eg：套娃 比如一个大盲盒里面套盲盒 一直套 知道最后一个盲盒被你打开 这个过程 叫递归 

//简单的实现打印集合所有的元素
var list = new List<int>() {1,2,3,4,5,6,7};
Circle(list);

Console.WriteLine("递归打印0~10的自然数");
int n = 10;
Recursion(n);


static void Circle(List<int> list){
    //循环打印
    var count = list.Count;
    var i = 0;
    while (count > 0) {
        Console.WriteLine(list[i]);
        i++;
        count--;
    }
}

static void Recursion(int x)
{
    if (x >= 0)
    {//递归条件就是x >= 0
        Console.WriteLine(x);
        Recursion(x - 1);
    }
    else { //基线条件
    //小于0 则跳出
    return;
    }  
}

Console.WriteLine("Hello, World!");
总结：（书中原文）

以上两种方法作用相同，但在我看来，第二种方法更清晰。递归只是让解决方案更清晰，并没有性能上的优势。实际上，在某些情况下，使用循环的性能更好。我很喜欢Leigh Caldwell在Stack Overflow上面说的一句话：”如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。“

很多算法都使用了递归，因此理解这种概念很重要。

Github 提交代码会有网络问题，后续代码可能会转向Gitee.