概述學習手册
Published on 2023-04-20 00:10:05 · 中文 · English · بالعربية · Español · हिंदीName · 日本語 · Русский язык
數據結構是一種組織數據以有效使用數據的系統方法。 以下術語是數據結構的基礎術語。
Interface-每個數據結構都有一個介面。 介面表示數據結構支援的一組操作。 介面僅提供支援的操作清單、它們可以接受的參數類型以及這些操作的返回類型。
Implementation-實現提供數據結構的內部表示。 實現還提供了數據結構操作中使用的演算法的定義。
數據結構的特徵
正確性-數據結構實現應正確實現其介面。 時間複雜度-運行時間或數據結構操作的執行時間必須盡可能小。 空間複雜度-數據結構操作的記憶體使用應盡可能少。需要數據結構
隨著應用程式變得越來越複雜和數據豐富,應用程式現在面臨三個常見問題。
數據搜索-考慮商店的 100 萬(106)個商品的庫存。 如果應用程式要搜索一個專案,它每次都必須在100萬(106)個專案中搜索一個專案,這會減慢搜索速度。 隨著數據的增長,搜索速度會變慢。
處理器速度-處理器速度雖然非常高,但如果數據增長到十億條記錄,則會受到限制。
多個請求-由於成千上萬的用戶可以同時在 Web 伺服器上搜索數據,即使是快速伺服器在搜索數據時也會失敗。
為了解決上述問題,數據結構來拯救。 可以將數據組織在數據結構中,這樣可能不需要搜索所有項目,並且幾乎可以立即搜索所需的數據。
執行時間案例
通常用於比較各種數據結構的執行時間的三種情況。
Worst Case-這是特定數據結構操作需要最大時間的情況。 如果一個操作的最壞情況時間是 ƒ(n),那麼這個操作將不會超過 ƒ(n) 時間,其中 ƒ(n) 表示 n 的函數。
Average Case-這是描述數據結構操作的平均執行時間的場景。 如果一個操作需要 ƒ(n) 時間執行,那麼 m 個操作將需要 mƒ(n) 時間。
Best Case-這是描述數據結構操作的最短執行時間的場景。 如果一個操作需要 ƒ(n) 時間執行,那麼實際操作可能需要時間作為隨機數,最大為 ƒ(n)。