大二上學期開了一門課叫數據結構,一開始跟著老師學,要想學好還是得花點功夫,等到學期末有一個關於數據結構的實訓,但是一星期下來,寫的項目,並沒有用上太多的數據結構,只用了一些簡單的棧隊列還有一點二分的思想,有些數據結構都是強加上去的,感覺這個項目並沒有太需要數據結構,沒有用武之地。
雖然我寫項目沒用上,肯定是因為我菜,我相信在大的項目裡,肯定用到了大量的數據結構,我現在不知道數據結構該用到哪裡,但我知道數據結構可以使程序的時間複雜度或者空間複雜度大大降低,下面我就拿我學的一些數據結構和算法來舉例說一下。
1.二分查找
二分的思想用的非常多,像二叉排序樹,二叉平衡樹,還有普通的二分查找。
給出一串有序的數,當想查找其中的一個數,普通的方法是從頭或者從尾開始遍歷的找,當數據量很小的時候,我相信是很快的,假如數據量是億級以上的,這種遍歷的方法就顯得十分慢了,平均查找長度比較大,當n比較大時,查找效率會很低,時間複雜度為O(n)。
但如果用二分查找的話,時間複雜度是O(log2n),這樣差別就非常大了。
2.線段樹
線段樹主要用於區間中的多次查詢,比如求區間和,區間最大,區間最小,區間更新等等。
給出一串數,當要求其中的一段區間的和的話,最直觀的方法就遍歷,如果多次查詢多個區間的和或者最大最小,用的時間將非常多,這肯定是不呢個接受的,這時候線段樹就有它明顯的優勢,可以快速的求出這一系列的東西。
線段樹是首先對這些數進行一個預處理,然後以後的每次詢問的時間複雜度是O(logN),這樣就非常的快了,不得不說,線段樹真的很神奇,有興趣的小夥伴可以去學習一下。
3.排序
排序有很多種,這裡就例舉一下各種排序的時間複雜度和空間複雜度
<hr>
數據結構中必要重要的幾個概念和算法。
★ 算法效率的度量和存儲空間需求
★ 線性表
★循環鏈表與雙向鏈表
★ 棧的表示與實現
★ 隊列
★ 串
★廣義表
★樹、二叉樹及樹的遍歷
★圖及圖的遍歷
★查找算法:順序查找,二分法,哈希
★ 排序:插入排序,快速排序,選擇排序,歸併排序等等。
★ 順序文件,索引文件
還有許多高級的數據結構,比如線段樹,字典樹,AC自動機,凸包等等的好多,我感覺數據結構是基礎,在做大項目的時候肯定能用到。‘
小編還是個菜鳥,分享一下自己的感受,大牛們如果不認同小編的看法,可以給小編提出來,小編會虛心接受的,如果喜歡,請點個關注,小編會努力的。