目錄
時間復雜度
空間復雜度
時間復雜度
大O記法
執行次數=執行時間
大O記法有以下幾個規則：
①用常數1取代運行時間中的所有加法常數;
如：O(5),用O(1)來表示，
②在修改后的運行次數中，只保留高階項;
如：O(2n^2+3n+1),則時間復雜度為O(n^2)
③如果最高階項存在，且常數因子不為1，則去除與這個項相乘的常數;
如：O(5n),則時間復雜度應該為O(n)
常見的時間復雜度：
| 描述 | 增長的數量級 | 說明 | 舉例 |
| 常數級別 | 1 | 普通陳述句 | 將兩個數相加 |
| 對數級別 | logN | 二分策略 | 二分查找 |
| 線性級別 | N | 回圈 | 找出最大元素 |
| 線型對數級別 | NlogN | 分治思想 | 歸并排序 |
| 平方級別 | N^2 | 雙層回圈 | 檢查所有元素對 |
| 立方級別 | N^3 | 三層回圈 | 檢查所有三元組 |
| 指數級別 | 2^N | 窮舉查找 | 檢查所有子集 |
復雜程度從低到高依次為：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)
空間復雜度
通常選擇空間換時間,一般說復雜度是指時間復雜度
java中有以下常見的記憶體占用情況
①java中基本資料型別記憶體占用情況:
| 資料型別 | 記憶體占用位元組數 |
|---|---|
| byte | 1 |
| short | 2 |
| int | 4 |
| long | 8 |
| float | 4 |
| double | 8 |
| boolean | 1 |
| char | 2 |
②計算機訪問記憶體都是一次一個位元組
③一個參考（機器地址）需要8個位元組表示
如：例如: Date date = new Date(),則date這個變數需要占用8個位元組來表示
④創建一個物件，比如new Date()，除了Date物件內部存盤的資料(例如年月日等資訊)占用的記憶體，該物件本身也有記憶體開銷，每個物件的自身開銷是16個位元組，用來保存物件的頭資訊，
⑤一般記憶體的使用，如果不夠8個位元組，都會被自動填充為8位元組
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/356976.html
標籤：java