Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之時間復(fù)雜度與空間復(fù)雜度
概述
從今天開始, 小白我將帶大家開啟 Jave 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.
算法的衡量標準
當我們需要衡量一個算法的的優(yōu)越性, 通常會使用時間復(fù)雜度 (Time Complexity) 和空間復(fù)雜度 (Space Complexity) 來衡量.
時間復(fù)雜度
時間復(fù)雜度 (Time Complexity) 通常用 O(n) 表示, 用來描述一個算法運行的時間.
時間復(fù)雜度 & 空間復(fù)雜度計算規(guī)則:
- 用常數(shù) 1 代替運行中的所有加減, lim n->∞cn = ∞
- 只保留最高項, lim n->∞ n^2 + an + b = lim n->∞ n^2
最優(yōu)時間復(fù)雜度
最優(yōu)時間復(fù)雜度指的是在最優(yōu)的情況下算法需要的運行時間.
平均時間復(fù)雜度
平均時間復(fù)雜度是指所有可能的輸入實例以等概率出現(xiàn)的情況下, 算法需要的運行時間.
最壞時間復(fù)雜度
最壞時間復(fù)雜度指的是在最壞的情況下算法需要的運行時間. 一般使用最壞時間復(fù)雜度作為時間復(fù)雜度.
O(1)
沒有循環(huán)結(jié)構(gòu), 只有普通加減的代碼時間復(fù)雜度為 O(1).
例如:
int i = 1; int j = 2; int k = i + j; // 1+2=3
O(n)
循環(huán) n 次的代碼的時間復(fù)雜度為 O(n).
例子:
int sum = 0; for (int i = 1; i < n; i++) { sum += i; }
O(n^2)
兩層循環(huán)嵌套的時間復(fù)雜度為 O(n^2). 如下例子, 需要進行 2n^2 次計算
例子:
int sum = 0; for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { sum += i; sum += j; } }
O(logN)
2^n = N, 所以會循環(huán) logN 次.
例子:
int sum = 0; for (int i = 0; i < n; i++) { sum += i; i *= 2; }
空間復(fù)雜度
空間復(fù)雜度 (Space Complexity) 定義為該算法所耗費的存儲空間.
O(1)
如果算法執(zhí)行所需要的臨時空間不會隨著變量的大小而變化, 那么空間復(fù)雜度就為 O(1).
例子:
int i = 1; int j = 2; int k = i + j; // 1+2=3
O(n)
長度為 n 的數(shù)組占用空間為 O(n).
例子:
int[] array = new int[n]
到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之時間復(fù)雜度與空間復(fù)雜度的文章就介紹到這了,更多相關(guān)Java 時間復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot多數(shù)據(jù)源讀寫分離的自定義配置問題及解決方法
這篇文章主要介紹了SpringBoot多數(shù)據(jù)源讀寫分離的自定義配置,我們可以通過自定義配置數(shù)據(jù)庫配置類來解決這個問題,方式有很多,不同的業(yè)務(wù)采用的方式也不同,下面我簡單的介紹我們項目的使用的方法2022-06-06SpringBoot中MyBatis-Flex的集成和使用實現(xiàn)
MyBatis-Flex是一個基于MyBatis的數(shù)據(jù)訪問框架,MyBatis-Flex能夠極大地提高我們的開發(fā)效率和開發(fā)體驗,本文主要介紹了SpringBoot中MyBatis-Flex的集成和使用實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2023-12-12Java+swing+Mysql實現(xiàn)商品銷售管理系統(tǒng)
基礎(chǔ)扎不扎實只有在實戰(zhàn)中才能顯現(xiàn),本篇文章手把手帶你用Java+swing+Mysql實現(xiàn)商品銷售管理系統(tǒng),大家可以在過程中查缺補漏,提升水平2022-01-01詳解MybatisPlus中@TableLogic注解的使用
@TableLogic一般用于實現(xiàn)數(shù)據(jù)庫數(shù)據(jù)邏輯刪除,本文我們將介紹 @TableLogic 注解的用法,以及每個屬性的實際意義和用法,感興趣的可以了解一下2022-06-06Java Spring JdbcTemplate基本使用詳解
JDBC已經(jīng)能夠滿足大部分用戶最基本的需求,但是在使用JDBC時,必須自己來管理數(shù)據(jù)庫資源如:獲取PreparedStatement,設(shè)置SQL語句參數(shù),關(guān)閉連接等步驟2021-10-10