【數據結構】第一講 —— 概論

【數據結構】第一講 —— 概論

文章目錄

  • 【數據結構】第一講 —— 概論
    • 1.1 基本概念和常用術語
    • 1.2 了解數據結構
      • 1. 數據結構
      • 2. 數據的邏輯結構
      • 3. 數據的物理結構(存儲結構)
      • 4. 數據的運算
    • 1.3 算法的描述和分析
      • 1.3.1 算法的描述
      • 1.3.2

1.1 基本概念和常用術語

  • 數據的基本單位是數據元素,最小單位是數據項
  • 一個數據元素可以由若干個數據項組成

1.2 了解數據結構

1. 數據結構

定義:數據結構指的是數據元素之間的相互關系,即數據的組織形式
內容:數據的邏輯結構、數據的存儲結構、數據的運算

2. 數據的邏輯結構

定義:從邏輯關系上描述數據,與數據元素的存儲結構無關,獨立于計算機
分類:線性結構和非線性結構

在這里插入圖片描述

3. 數據的物理結構(存儲結構)

定義:數據元素及其關系在計算機內的存儲方式,稱為數據的存儲結構
實現方法:順序存儲、鏈接存儲、索引存儲、散列存儲
在這里插入圖片描述

4. 數據的運算

定義:對數據元素施加的操作(行為)
內容:最常用的插入、刪除、查找、排序等。

插入:增加節點、入棧、入隊
刪除:刪除節點、出棧、出隊
查找:二分查找、散列查找
排序:選擇排序、快速排序

1.3 算法的描述和分析

1.3.1 算法的描述

算法的定義:
算法是對特定問題的求解方法(步驟)的一種描述,是指令的有限序列,其中每一條指令表示一個或多個操作

算法的五大基本準則

  • 有窮性:一個算法必須總是在執行有窮步之后結束,且每一步都在有窮時間內完成。
  • 確定性:算法中每一條指令必須由確切的含義,不存在二義性
  • 可行性:一個算法是能行的。即算法描述的操作都可以通過已經實現的基本運算執行有限次來實現。
  • 輸入:一個算法有零個或多個輸入,這些輸入取自于某個特定的對象集合
  • 輸出:一個算法有一個或多個輸出,這些輸出是同輸入有著某些特定關系的量

1.3.2

算法的分析因素

在這里插入圖片描述

健壯性又叫魯棒性

時間復雜度
算法中基本操作重復執行的次數是問題規模n的某個函數,其時間量度記作T(n) = O(f(n)) ,稱作算法的漸進時間復雜度(Asymptotic Time complexity),簡稱時間復雜度。
一般地,常用最深層循環內地語句中原操作地執行頻度(重復執行地次數)來表示。

在這里插入圖片描述

for (i = 1; i <= n; ++i) {++x;s+=x;
}

時間復雜度為:O(n) ,即為線性階

for (i = 1; i <= n; ++i) {for (j = 1; j <= n; ++j) {++x; s+=x}
} 

時間復雜度為:O(n^2) ,即平方階

for (i = 1; i <= n; ++i) {for (j = 1; j <= n; ++j) {c[i][j] = 0;for (k = 1; k <= n; ++k) {c[i][j] += a[i][k] * b[k][j];}} 
}

需要注意其中 c[i][j] = 0 不能納入計算時間復雜度的語句。需要計算最深層循環c[i][j] += a[i][k] * b[k][j]; 的語句。
時間復雜度為:O(n^3) ,即為立方階

空間復雜度

空間復雜度是指算法編寫成程序后,在計算機中運行時所需存儲空間大小的度量,該存儲空間一般包括三個方面:

  • 指令常數變量所占用的存儲空間;
  • 輸入數據所占用的存儲空間;
  • 輔助(存儲)空間。

一般地,算法的空間復雜度指的是輔助空間

在這里插入圖片描述

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/89849.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/89849.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/89849.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

全面解析MySQL(2)——CRUD基礎

1.CreateCreate(創建)&#xff1a;添加新數據到數據庫中#基礎語法 insert into table_name (column1,column2,column3, ...) values (value1,value2,value3, ...);1.1 單行全列插入value中值的數量和順序必須和column?致describe demo1; -----------------------------------…

某外企筆試總結——純C語言

這里寫自定義目錄標題一、sizeof 計算&#xff08;32位環境&#xff09;二、簡答題三、數據存儲區域與可修改性四、字符串比較輸出及原因五、數組指針運算輸出六、字符串倒序代碼錯誤排查七、下面程序可以把1維數組轉為2維數組&#xff0c;然后調用 printArr2D 打印出數組內容&…

Qt Graphs 模塊擬取代 charts 和 data visualization還有很長的路要走

近期關注 Qt 6.10 的分支進展&#xff0c; 發現了 Qt 6.10 的 charts 和 data visualization &#xff08;以下簡稱 DV&#xff09;已經被deprecated, 功能將會合并到 graphs 模塊。如果后面 charts\ DV 被棄用&#xff0c;那算是很大的API變化了。從Qt 6.5 以后開始引入的 gra…

2025牛客暑期多校訓練營2(部分補題)

題目鏈接&#xff1a;牛客競賽_ACM/NOI/CSP/CCPC/ICPC算法編程高難度練習賽_牛客競賽OJ B Bitwise Perfect 思路 考慮到由&#xff0c;那么只有變小的時候對答案的貢獻才能夠減少&#xff0c;從二進制的角度考慮什么時候變小&#xff0c;只有min(x,y)中的最高位1異或之后變…

Nginx的location匹配規則

Nginx的location匹配規則 為什么你的Nginx配置總是不生效&#xff1f; 改了Nginx配置無數次&#xff0c;reload命令執行了幾十遍&#xff0c;瀏覽器訪問時卻依然返回404&#xff1f;運維工程師小張上周就遇到了這個問題&#xff1a;明明配置了location /static/ { root /var/ww…

USB 2.0 vs USB 3.0:全面技術對比與選擇指南

USB 2.0 vs USB 3.0&#xff1a;全面技術對比與選擇指南 引言 在當今數字時代&#xff0c;USB接口已成為連接設備與計算機的最普遍標準之一。從2000年USB 2.0的發布到2008年USB 3.0的問世&#xff0c;USB技術經歷了顯著的演進。本文將深入比較這兩種廣泛使用的USB標準&#xff…

DApp架構設計與開發流程指南

目錄 DApp架構設計與開發流程指南 引言:DApp的核心特性 一、DApp架構設計 1.1 分層架構設計 各層核心組件: 1.2 典型架構模式 1.2.1 全去中心化架構 1.2.2 混合架構(推薦) 二、開發流程 2.1 敏捷開發流程 2.2 詳細開發階段 階段1:需求分析與設計(1-2周) 階段2:智能合約…

Windows下odbc配置連接SQL Server

一、查看SQL Server服務是否啟動打開SQL Server 2022配置管理器查看SQL Server運行狀態&#xff0c;可以設置 啟動或停止服務二、windows下如何配置ODBC數據源1、Windows搜索欄中輸入“ODBC數據源管理器”并選擇“以管理員身份運行”來打開它2、添加新的數據源ODBC數據源管理器…

MySQL—表設計和聚合函數以及正則表達式

文章目錄一、第一范式&#xff08;原子性&#xff09;二、第二范式&#xff08;消除部分依賴&#xff09;三、第三范式&#xff08;消除傳遞依賴&#xff09;四、表設計五、聚合函數六、正則表達式MySQL 的三大范式&#xff08;1NF、2NF、3NF&#xff09;是關系型數據庫設計的核…

基于Electron打包jar成Windows應用程序

基于Electron打包jar成Windows應用程序簡介注意編譯及命令&#xff1a;運行效果登錄界面用戶管理界面界面全屏鎖屏界面文檔查看界面簡介 本文介紹了一種將maven jar包打包成Windows下EXE可執行程序的方法。 Maven打包Java Web應用成jar&#xff0c;Electron封裝jar成Windows …

Autosar RTE實現觀測量生成-基于ETAS軟件

文章目錄前言觀測量定義arTypedPerInstanceMemoryPorts Measurable工具鏈配置及使用Port中的配置arTypedPerInstanceMemory觀測量生成文件分析總結前言 之前我們在XCP中&#xff0c;對于標定量和觀測量并沒有嚴格按照Autosar標準中定義&#xff0c;Autosar RTE中對標定量和觀測…

【REACT18.x】creat-react-app在添加eslint時報錯Environment key “jest/globals“ is unknown

今天在創建新項目的時候&#xff0c;給cra創建的項目添加eslint支持&#xff0c;出現如下報錯 添加eslint npx eslint --init頁面報錯 Compiled with problems:ERROR [eslint] package.json eslint-config-react-app/jest#overrides[0]:Environment key "jest/globals&…

Linux的例行性工作 -- (練習)

1、atd和crond兩個任務管理程序的區別 答&#xff1a; atd 專為一次性任務設計&#xff0c;允許用戶在特定未來時間點&#xff08;絕對或相對時間&#xff09;執行單次命令后就結束。 crond 則是周期性任務的調度核心&#xff0c;通過配置文件&#xff08;crontab&#xff09;實…

《Java語言程序設計》1.6 復習題

1.6.1 什么是Java語言規范?計算機有嚴格的使用規則。如果編寫程序時沒有遵循這些規則&#xff0c;計算機就不能理解程序。Java語言規范和Java API定義了Java的標準。Java語言規范(Java language specification)是對Java程序設計語言的語法和語義的技術定義。應用程序接口(Appl…

【機器學習深度學習】什么是量化?

目錄 前言 一、量化的基本概念 1.1 量化對比示例 1.2 量化是如何實現的&#xff1f; 二、為什么要進行量化&#xff1f; 2.1 解決模型體積過大問題 2.2 降低對算力的依賴 2.3 加速模型訓練和推理 2.4 優化訓練過程 2.5 降低部署成本 小結&#xff1a;量化的應用場…

告別 T+1!解密金融級實時數據平臺的構建與實踐

在數字金融浪潮下&#xff0c;數據處理的“實時性”已不再是加分項&#xff0c;而是逐漸成為決定業務價值的核心競爭力。然而&#xff0c;金融機構在追求實時的道路上&#xff0c;往往陷入一個新的困境&#xff1a;實時分析系統與離線大數據平臺形成了兩套獨立的“煙囪”&#…

[Python] -項目實戰7- 用Python和Tkinter做一個圖形界面小游戲

一、為什么從小游戲入門GUI? 趣味性強:小游戲直觀、有趣,一學就上手。 系統掌握事件驅動:了解按鈕點擊、鍵盤響應、圖形刷新機制。 扎實基礎:為日后構建更復雜應用奠定 GUI 編程基礎。 二、選定游戲:猜數字小游戲 ?? 這個小游戲界面簡單,核心機制是:3 個按鈕分別…

【18】MFC入門到精通——MFC(VS2019)+ OpenCV 顯示圖片的3種方法

MFC (VS2019)+ OpenCV,顯示圖片的3種方法 1 方法介紹 2 方法一:嵌套OpenCV窗口顯示圖片 2.1 建立供工程 添加控件 2.2 引用頭文件 2.3 找到OnInitDialog()函數,在其中添加如下代碼 2.4 在button觸發函數中加入代碼(就是你雙擊button進入的函數) 2.5 注意事項 3 方法二:…

以“融合進化 智領未來”之名,金倉Kingbase FlySync:國產數據庫技術的突破與創新

目錄開篇&#xff1a;國產數據庫的歷史性跨越一、KFS 產品定位及發展歷程回顧1.1 Kingbase FlySync 發展1.2 Kingbase FlySync與Oracle GoldenGate的對比分析1.2.1 Kingbase FlySync 功能優勢1.2.2 技術架構對比1.2.3 性能與擴展性二、數字化時代的新挑戰2.1 決策實時性要求越來…

服務器配置錯誤漏洞

文章目錄一、文件解析漏洞1.Apache HTTPD多后綴解析漏洞二、目錄遍歷漏洞1.Apache目錄遍歷漏洞2.Nginx目錄穿越漏洞服務器配置錯誤漏洞指因服務器&#xff08;含系統、Web服務、數據庫等&#xff09;的參數設置、權限分配、組件配置等不當&#xff0c;導致的安全問題&#xff0…