C#数据结构与算法学习

男娘i 2021-09-14 17:38 354阅读 0赞

#### 第一章 绪论 ####

**1.数组与链表**  
数组所分配的存储空间是连续的，所以数组天生就具有实现数据顺序存储结构的能力；  
链式存储结构（Linked Storage Structure）是通过数据元素在计算机存储器中的相对位置来表示出数据元素的逻辑关系，**一般把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中**。

2.实现算法的语言级别越高，其执行效率相对越低。

3.一般而言，编译的执行效率高于解释，但解释具有更大的灵活性。（C\#/Java || Python/JS）

**4.算法的时间复杂度**  
算法的时间度，就是看算法执行的一个频度。一层n遍for循环，T(n) = O(n),两层n遍for循环，T（n） = O(n2)等。  
例子：

x = n;      /* n > 1*/
    y  = 0;
    while(x >= (y + 1)*(y + 1))
    {
        y = y + 1;
    }

这是一重循环的程序，while循环的循环次数为√n，所以，T(n) = O(√n)。  
这个时候着重看while里面会循环多少遍。设z = y + 1;

while(x >= z²)
    { z++; }

所以这个时候，只需要执行√n遍的时候，随着z的增加，就会大于等于x即n，所以执行的频度为√n。

**1.5 递归**  
以下利用计算n!来理解递归的过程：  
首先把定义了解以下，  
![这里写图片描述][70]  
代码：

static void Main(string[] args)
            {
                var x = Fact(3);
                Console.WriteLine("3! = " + x);
                Console.ReadLine();
            }
    
            private static int Fact(int n)
            {
                if (n > 1)
                {
                    return n * Fact(n - 1);
                }
                else
                {
                    return 1;
                }
            }

输出：3! = 6  
自身调用自身的方法，自给自足。那这个方法的时间复杂度是T(n) = O(n)吧~  
**1.6 接口**  
接口是类与类之间的协定，为什么要使用接口呢？个人感觉下面这个例子很形象：  
[http://blog.csdn.net/zbjlu/article/details/4075154][http_blog.csdn.net_zbjlu_article_details_4075154]  
下面的这个详解很详细，非常有助理解接口：  
[http://www.cnblogs.com/tianxue/p/5641555.html\#title1][http_www.cnblogs.com_tianxue_p_5641555.html_title1]  
什么是接口？

> 接口是一种用来定义程序的协议，它描述可属于任何类或结构的一组相关行为。  
> 接口是一组规则的集合，它规定了实现本接口的类或接口必须拥有的一组规则。体现了自然界“如果你是……则必须能……”的理念。  
> 接口是在一定粒度视图上同类事物的抽象表示。因为“同类事物”这个概念是相对的，它因为粒度视图不同而不同。

为什么使用接口？而不直接实现？

> 接口的使用并非总是从设计的角度来考虑。接口和C\#其他语法现象一样，共同构成了C\#整个语言体系。  
> 接口的意义在于 抽象、不拘细节,从而使同类事物在同一高度具有通用及可替代性。  
> 关于解耦，并不是接口能解耦，而是抽象能解耦 接口只是手段,如果两个事物有必然联系，那么就不会出现完全解耦，只能耦合转移。  
> —— from [http://bbs.csdn.net/topics/380040137][http_bbs.csdn.net_topics_380040137]

**1.7 泛型**  
泛型的主要思想就是将算法与数据结构完全分离开来，使得一次定义的算法能够作用于多种数据结构，从而实现高度可重用的开发。通过泛型可以定义类型安全的数据结构，而没有必要使用实际的数据类型。  
本以为泛型会影响性能，但是做了一个简单的实验，在简单的输入返回上，并不会有太大的影响。

static void Main(string[] args)
            {
                DateTime d1 = DateTime.Now;
                for (int i = 0; i < 1000000000; i++)
                {
                    var testOne = AddArray(i);
                }
                DateTime d2 = DateTime.Now;
                Console.WriteLine("用时：" + (d2 - d1).TotalMilliseconds);
                Console.ReadLine();
            }
    
            private static T AddArray<T>(T x)
            {
                return x;
            }
    
            private static int AddArray(int i)
            {
                return i;
            }

在本机测试，循环1000000000遍，用时大致相同，14966ms左右。

[70]: /images/20210615/dbf2739e2be94ec19615d4b5b50d73f0.png
[http_blog.csdn.net_zbjlu_article_details_4075154]: http://blog.csdn.net/zbjlu/article/details/4075154
[http_www.cnblogs.com_tianxue_p_5641555.html_title1]: http://www.cnblogs.com/tianxue/p/5641555.html#title1
[http_bbs.csdn.net_topics_380040137]: http://bbs.csdn.net/topics/380040137