Java 資料結構與演算法 - 概述

什麼是資料結構？

資料結構是一種以特定方式組織資料，以便高效使用的方法。以下術語是資料結構的基礎術語。

• 介面 - 每個資料結構都有一個介面。介面表示資料結構支援的操作集。介面僅提供支援的操作列表、它們可以接受的引數型別以及這些操作的返回型別。

• 實現 - 實現提供了資料結構的內部表示。實現還提供了資料結構操作中使用的演算法的定義。

資料結構的特徵

• 正確性 - 資料結構實現應正確實現其介面。

• 時間複雜度 - 資料結構操作的執行時間或執行時間應儘可能短。

• 空間複雜度 - 資料結構操作的記憶體使用量應儘可能少。

資料結構的必要性

隨著應用程式變得越來越複雜和資料豐富，如今應用程式面臨三個常見問題。

• 資料搜尋 - 考慮一個商店擁有 100 萬 (10⁶) 件商品的庫存。如果應用程式要搜尋一件商品。它每次都必須在 100 萬 (10⁶) 件商品中搜索商品，從而減慢搜尋速度。隨著資料量的增長，搜尋會變得越來越慢。

• 處理器速度 - 儘管處理器速度非常高，但如果資料增長到數十億條記錄，它仍然會受到限制。

• 多請求 - 由於數千名使用者可以同時在 Web 伺服器上搜索資料，即使是最快的伺服器在搜尋資料時也會出現故障。

為了解決上述問題，資料結構可以提供幫助。資料可以以某種方式組織到資料結構中，這樣就不需要搜尋所有專案，並且可以幾乎立即搜尋所需的資料。

執行時間案例

通常有三種情況用於以相對方式比較各種資料結構的執行時間。

• 最壞情況 - 這是特定資料結構操作可能花費的最長時間。如果操作的最壞情況時間為 ƒ(n)，則此操作花費的時間不會超過 ƒ(n)，其中 ƒ(n) 表示 n 的函式。

• 平均情況 - 這表示資料結構操作的平均執行時間。如果操作執行時間為 ƒ(n)，則 m 個操作將花費 mƒ(n) 時間。

• 最佳情況 - 這表示資料結構操作的最小可能執行時間。如果操作執行時間為 ƒ(n)，則實際操作可能花費的時間為隨機數，其最大值為 ƒ(n)。