欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C#數(shù)據(jù)結構與算法揭秘一

 更新時間:2012年11月01日 20:47:14   作者:  
本文一介紹了數(shù)據(jù)結構的基本概念 而介紹了算法的基本概念,并且重點討論了算法時間復雜度,并且用程序予以證明

這里,我們 來說一說C#的數(shù)據(jù)結構了。

①什么是數(shù)據(jù)結構。數(shù)據(jù)結構,字面意思就是研究數(shù)據(jù)的方法,就是研究數(shù)據(jù)如何在程序中組織的一種方法。數(shù)據(jù)結構就是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。 程序界有一點很經(jīng)典的話,程序設計=數(shù)據(jù)結構+算法。用源代碼來體現(xiàn),數(shù)據(jù)結構,就是編程。他有哪些具體的關系了,

(1) 集合(Set):如圖 1.1(a)所示,該結構中的數(shù)據(jù)元素除了存在“同屬于一個集合”的關系外,不存在任何其它關系。 集合與數(shù)學的集合類似,有無序性,唯一性,確定性。

(2) 線性結構(Linear Structure):如圖 1.1(b)所示,該結構中的數(shù)據(jù)元素存在著一對一的關系。我們.net程序員做的最多的工作就是對數(shù)據(jù)庫的表crud,二表的最小的數(shù)據(jù)單元是行。每行數(shù)據(jù)是最明顯的線性結構。 
(3) 樹形結構(Tree Structure):如圖 1.1(c)所示,該結構中的數(shù)據(jù)元素存在著一對多的關系?,F(xiàn)實中,家族關系中是最明顯的樹形結構。如圖所示

而對于我們.net程序員來說,操作的樹形控件是也是最明顯的樹形結構


(4) 圖狀結構(Graphic Structure):如圖 1.1(d)所示,該結構中的數(shù)據(jù)元素存在著多對多的關系。在現(xiàn)實中,圖應用的太多了,如圖所示:

對于我們。net程序員應用的較少,當你用C++作一些底層應用,如搜索引擎,地圖導航應用的蠻多的。

以上是針對數(shù)據(jù)結構的介紹。

做過開發(fā)的人員都知道這個道理,算法與數(shù)據(jù)結構和程序的關系非常密切。 進行程序設計時,先確定相應的數(shù)據(jù)結構,然后再根據(jù)數(shù)據(jù)結構和問題的需要設計相應的算法。

②那什么是算法了?算法,就是計算的方法了,就是解決問題的方案,就是對某一特定類型的問題的求解步驟的一種描述, 是指令的有限序列。 用源代碼體現(xiàn),算法就是編程的體現(xiàn)。一個算法應該具備以下 5個特性:

1、有窮性(Finity):一個算法總是在執(zhí)行有窮步之后結束,即算法的執(zhí)行時間是有限的。我們初學.net時候,經(jīng)常寫著死循環(huán),這不是算法,因為這是無窮的。 
2、確定性(Unambiguousness):算法的每一個步驟都必須有確切的含義,即無二義,并且對于相同的輸入只能有相同的輸出。對于我們.net程序員寫出二義性的源代碼,編譯器根本讓你通不過。 
3、輸入(Input):一個算法具有零個或多個輸入。它即是在算法開始之前給出的數(shù)據(jù)結構這些輸入是某數(shù)據(jù)結構中的數(shù)據(jù)對象。編程是解決問題的,如果不能輸入的話,怎么解決問題了。 
4、 輸出(Output):一個算法具有一個或多個輸出,并且這些輸出與輸入之間存在著某種特定的關系。 編程就是解決了生活中問題,你不讓用戶看到最后的結果,這就失去了編程的意義。
5、 能行性(realizability):算法中的每一步都可以通過已經(jīng)實現(xiàn)的基本運算的有限次運行來實現(xiàn)。這與有窮性息息相關。

那算法的評價標準又是什么了?

評價一個算法優(yōu)劣的主要標準如下:1、 正確性(Correctness)。2、可讀性(Readability)3、健壯性(Robustness)。4、運行時間(Running Time)。5、占用空間(Storage Space)。

前3個性質(zhì),我們很好拿捏。與我們程序員息息相關的是運行時間與占用空間。然而,隨著硬件越來越便宜,面對占用空間,我們無非增加硬件。面對海量數(shù)據(jù),我們尤為關心是運行時間(Running Time)。這此時的計算機的運行時間由以下因素決定:

1、硬件條件。包括所使用的處理器的類型和速度(比如,使用雙核處理器還是單核處理器) 、可使用的內(nèi)存(緩存和 RAM)以及可使用的外存等。
2、實現(xiàn)算法所使用的計算機語言。實現(xiàn)算法的語言級別越高,其執(zhí)行效率相對越低。
3、所使用的語言的編譯器/解釋器。一般而言,編譯的執(zhí)行效率高于解釋,但解釋具有更大的靈活性。
4、所使用的操作系統(tǒng)軟件。操作系統(tǒng)的功能主要是管理計算機系統(tǒng)的軟件和硬件資源,為計算機用戶方便使用計算機提供一個接口。各種語言處理程序如編譯程序、解釋程序等和應用程序都在操作系統(tǒng)的控制下運行。

 評價運行時間就是一個算法時間復雜度,  一個算法的時間復雜度(Time Complexity)是指該算法的運行時間與問題規(guī)模的對應關系。

算法中的基本操作一般是指算法中最深層循環(huán)內(nèi)的語句,因此,算法中基本操作語句的頻度是問題規(guī)模n的某個函數(shù)f(n),記作:T(n)=O(f(n))。其中“O”表示隨問題規(guī)模n的增大,算法執(zhí)行時間的增長率和f(n)的增長率相同,或者說,用“O”符號表示數(shù)量級的概念。  這些 都只是一些理論的概念,我們這里用計時器來證明這個理論概念。

如:

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

從理論上分析這是一重循環(huán)的程序,while 循環(huán)的循環(huán)次數(shù)為 n,所以,該程序段中語句①的頻度是 n,則程序段的時間復雜度是 T(n)=O(n) 。

從程序上驗證,當n=10時,運行結果如圖所示:

當n=100000時,運行結果如圖所示

由此證明,其中算法的時間復雜度確實是接近于O(n)

for(i=1;i<n;++i) {
for(j=0;j<n;++j)
{
A[i][j]=i*j; ①
}
}

理論上解釋為這是二重循環(huán)的程序,外層for循環(huán)的循環(huán)次數(shù)是n,內(nèi)層for循環(huán)的循環(huán)次數(shù)為n,所以,該程序段中語句①的頻度為n*n,則程序段的時間復雜度
為T(n)=O(n²) 。

從程序上證明,當n=10,其運行效果如圖所示:

當n=100000,其運行效果如圖所示:

由此證明,其中算法的時間復雜度確實是接近于O(n²)

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

這是一重循環(huán)的程序,while 循環(huán)的循環(huán)次數(shù)為 n,所以,該程序段中語句①的頻度是 n,則程序段的時間復雜度是 T(n)=O(√n) 。

從程序證明:當n=10時,運行效果如圖所示:

當n=100000時,運行效果如圖所示:

由此證明,其中算法的時間復雜度確實是接近于O(√n)

本文一介紹了數(shù)據(jù)結構的基本概念 而介紹了算法的基本概念,并且重點討論了算法時間復雜度,并且用程序予以證明。

相關文章

  • C#生成putty格式的ppk文件

    C#生成putty格式的ppk文件

    這篇文章介紹了C#生成putty格式ppk文件的方法,文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-07-07
  • C#下使用XmlDocument操作XML詳解

    C#下使用XmlDocument操作XML詳解

    本文詳細講解了C#使用XmlDocument操作XML的方法,文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-06-06
  • C#執(zhí)行DOS命令的方法

    C#執(zhí)行DOS命令的方法

    這篇文章主要介紹了C#執(zhí)行DOS命令的方法,涉及針對進程的調(diào)用以及系統(tǒng)DOS命令的使用,具有不錯的實用價值,需要的朋友可以參考下
    2014-11-11
  • C#實現(xiàn)讓窗體獲得焦點的方法示例

    C#實現(xiàn)讓窗體獲得焦點的方法示例

    這篇文章主要介紹了C#實現(xiàn)讓窗體獲得焦點的方法,涉及C#窗體事件相關操作技巧,需要的朋友可以參考下
    2017-06-06
  • C#實現(xiàn)在listview中插入圖片實例代碼

    C#實現(xiàn)在listview中插入圖片實例代碼

    這篇文章主要介紹了C#實現(xiàn)在listview中插入圖片實例代碼的相關資料,需要的朋友可以參考下
    2017-03-03
  • C#生成不重復隨機字符串類

    C#生成不重復隨機字符串類

    這篇文章主要介紹了C#生成不重復隨機字符串類,涉及C#隨機數(shù)與字符串的操作技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-03-03
  • c#使用微信接口開發(fā)微信門戶應用中微信消息的處理和應答

    c#使用微信接口開發(fā)微信門戶應用中微信消息的處理和應答

    這篇文章主要介紹了c#使用微信接口開發(fā)微信門戶中的微信消息的處理和應答的過程,需要的朋友可以參考下
    2014-03-03
  • C#中委托的基礎入門與實現(xiàn)方法

    C#中委托的基礎入門與實現(xiàn)方法

    這篇文章主要給大家介紹了關于C#中委托的基礎入門與實現(xiàn)方法的相關資料,究竟什么是委托,用最通俗易懂的話來講,你就可以把委托看成是用來執(zhí)行方法(函數(shù))的一個東西,需要的朋友可以參考下
    2021-08-08
  • C#中面向?qū)ο缶幊虣C制之繼承學習筆記

    C#中面向?qū)ο缶幊虣C制之繼承學習筆記

    這篇文章主要介紹了C#中面向?qū)ο缶幊虣C制之繼承學習筆記,本文給出一個簡單子實例講解C#中的繼承,并講解了一些C#繼承的知識技巧,需要的朋友可以參考下
    2015-01-01
  • C#?md5?算法實現(xiàn)代碼

    C#?md5?算法實現(xiàn)代碼

    相對C#來說,md5算法就相對簡單很多,因為?System.Security.Cryptography;?已經(jīng)包含了md5算法。所以我們只需創(chuàng)建MD5類對象即可實現(xiàn)md5算法,今天通過本文給大家介紹C#?md5?算法實現(xiàn),感興趣的朋友一起看看吧
    2022-11-11

最新評論