開發與維運

程序員必備——數據結構入門

前言:數據結構與算法作為計算機經典的基礎理論課程,同時作為計算機類專業考研課程,並且在校招面試時常被提及,其重要性可見一斑。除此之外,學習這門課程有助於我們用編程去解決、思考問題,設計出更簡潔、效率更高的代碼。

一.課程概述

  • 數據結構課程研究什麼?

    • 內存中基本數據組織和數據處理的方法
    • 非數值問題
  • 通過學習數據結構獲得什麼?

    • 經典數據結構和經典算法的基本原理
  • 學習重點

    • 數據結構的邏輯特性和存儲結構設計
    • 數據結構算法設計基本方法和分析方法
    • 利用數據結構解決實際問題

二.基本概念與術語

  • 數據

    • 能輸入到計算機中,被程序識別和處理的一切事物的符號化表示
  • 數據元素

    • 數據的基本單位
  • 數據項

    • 構成數據元素的最小單位
  • 存儲結構(由想法到算法)

    • 順序存儲結構
    • 鏈式存儲結構
  • 邏輯結構(由問題到想法)

    • 一種邏輯結構可由多種存儲結構實現
  • 數據結構

    • 邏輯結構
    • 存儲結構
    • 數據運算
  • 抽象數據類型(ADT)

    ADT 抽象數據類型名{
        數據對象的定義
        數據元素之間的邏輯關係定義
        基本運算定義
    }ADT
  • 算法的定義

    • 基於存儲結構的運算實現的步驟
    • 滿足有窮性確定性可行性
    • 有0個或多個輸入,1個或多個輸出
  • 什麼是好的算法

    • 正確性:對於合法輸入,算法能得出正確結果
    • 健壯性:對於非法輸入,算法能做出特別處理
    • 可理解性:算法容易理解、實現
    • 高效性:具有較短執行時間並佔用較少空間
    • 可修改、可拓展性

三.算法分析

  • 時間複雜度

    • 是算法求解問題規模n的函數,T(n)=F(n),F(n)是基本語句的執行頻度
    • 增長率:忽略低次冪和最高次冪係數
  • 分析規則

    • 加法規則:針對並列程序段
    • 乘法規則:針對嵌套程序段
  • 例子

  • 常見的時間複雜度

    O(1)<(log2n)<(n)<(nlog2n)<(n²)<...<(2的n次方)<(n!)
  • 空間複雜度

    • 除去輸入輸出佔用空間,算法臨時佔用的存儲空間
    • S(n)=O(f(n))

完整內容可以訪問我的個人博客:數據結構 515code.com

Leave a Reply

Your email address will not be published. Required fields are marked *