C#基本概念：时间复杂度，空间复杂度，递归与接口

在开始前先提出二个C#基本概念：时间复杂度与空间复杂度。

时间复杂度是指该算法的运行时间与问题规模的对应的关系。时间复杂度用T(n)=0(f(n)来表示，其中0表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，如果一个没有循环的代码，算法的执行频度是不会变的，记作0(1)。当算法中有一个一重循环，那执行频率就会呈线性增长0(n*n)...等等。

光看这个表达式还是很抽象的，下面来二个例子：

1、

i=n;  



x=0;  




while(x< i)  



{  



 x=x+1;   //这是个是一重循环，时间复杂度为T(n)=0(n)  



} 

2、

int re=0;  



for(int i=0;i< n;i++)  



{  



  for(int k=0;k< n;k++)  



  {  



    re=re+(i*j);  //这是个是二重循环，时间复杂度为T(n)=0(n*n)  



  }  


} 

空间复杂度是指该算法的运行过程中临时占用的存储空间的大小。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。

下面再次提出两个C#基本概念:递归与接口

递归是指算法调用自己来完成它的工作。这个概念无论在算法上还是实现代码编写中都很重要，经常大家去面试时，都会有一条这样的考题，在深圳这边，我以前面试过的公司一般都有一条兔子数列。按我的看法，我在做题时就是使用递归算法来做的。

例：1，1，2，3，5，8，13，21，34，55，89，……求第20位

其实就是一个这样的递归关系：  f(n):=f(n-1)+f(n-1)

接口是指类之间交互遵守的一个协议。

下面列出常用的接口IComparable,IEnumerable,IEnumerator,ICollection,IDictionary,IList

包插其对应的泛型接口。

下面看一个接口的例子：

public interface IBook  


{  



    string ShowBook();  




    string GetTitle();  




    int GetPages();  




    void SetPages(int pages);  



}  


 



public class NewBook : IBook  



{  



    public string title;  




    public int pages;  




    public string author;  



 



    public NewBook(string title, string author, int pages)  



    {  



        this.title = title;  




        this.author = author;  




        this.pages = pages;  



    }  


 



    public string GetTitle()  



    {  



        return title;  



    }  


 



    public int GetPages()  



    {  



        return pages;  



    }  


 



    public void SetPages(int pages)  



    {  



        this.pages = pages;  



    }  


 



    public string ShowBook()  



    {  



        return title + "," + author + "," + pages;  



    }  


 


}  


 



private void button1_Click(object sender, EventArgs e)  



{  



   NewBook nb = new NewBook("A", "James", 200);  



   richTextBox1.Text = nb.ShowBook();  


}