Java時間和空間的復雜度算法是什么

本篇內(nèi)容主要講解“Java時間和空間的復雜度算法是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java時間和空間的復雜度算法是什么”吧!

前言

1.在平常我們所說的時間復雜度一般說的都是算法的最壞情況；
2.時間復雜度度是一個函數(shù)，這個函數(shù)只能大致估一下這個算法的時間復雜度；
3.空間復雜度是個算法在運行過程中額外占用存儲空間大小的量度。

一、算法效率

算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度。 時間復雜度主要衡量的是一個算法的運行速度，而空間復雜度主要衡量一個算法所需要的額外空間。

二、時間復雜度

1.時間復雜度的概念

在計算機科學中，算法的時間復雜度是一個函數(shù)，它定量描述了該算法的運行時間。

算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。

• 一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比例；

• 算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。

2.大O的漸進表示法

實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進表示法。

• 大O符號（Big O notation）：是用于描述函數(shù)漸進行為的數(shù)學符號

(1)推導大O階方法

1. 用常數(shù)1取代運行時間中的所有加法常數(shù)。

2. 在修改后的運行次數(shù)函數(shù)中，只保留最高階項。

3. 如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階

代碼如下（示例）：

• 所以func方法的執(zhí)行次數(shù)為 1+N2+2*N+1+10

我看到func的執(zhí)行次數(shù)，如果當我們的N非常大時，假設N = 100，那么這里的+1和+10是不是可以忽略了，因為1002=10000,在一萬面前+1和+10可以說是微乎其微了，所以+1和+10沒什么區(qū)別。

這就用到了前面說了推導大O階方法。

• 用常數(shù)1取代運行時間中的所有加法常數(shù)。

就變成了 1+N2+2*N+1+1；

再來看

• 在修改后的運行次數(shù)函數(shù)中，只保留最高階項。

簡化后 N2

• 如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階。

這里我們的最高階項是2，但前面沒有常數(shù)所以沒必要去除，如果N2前面還有個2就是2N2就要去除2變成 N2；

所以使用大O的漸進表示法以后，F(xiàn)unc的時間復雜度為 O(N2)。

通過上面我們會發(fā)現(xiàn)大O的漸進表示法去掉了那些對結(jié)果影響不大的項，簡潔明了地表示出了執(zhí)行次數(shù)。時間復雜度是一個函數(shù)，只能大致估一下這個算法的時間復雜度。

3.時間復雜度的三種情況

另外有些算法的時間復雜度存在最好、平均和最壞情況。

(1) 最壞情況

• 最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界) 也就是 O(N)；

這里的N代表的是問題的規(guī)模；

(2)最好情況

• 任意輸入規(guī)模的最小運行次數(shù)(下界) 也就是 O(1)；

(3)平均情況

• 任意輸入規(guī)模的期望運行次數(shù)；

注意：這里的平均情況并不是最好和最壞情況相加的平均值，而是我們期望運行的次數(shù)，有時候平均情況可能和最好或者是最壞情況一樣。

• 在平常我們所說的時間復雜度一般說的都是算法的最壞情況。

4.常見時間復雜度計算舉例

1.例子

示例1：

1+2*N+1+10 通過推導大O階方法后:時間復雜度為 O(N)；

示例2：

時間復雜度為：O(M+N)；

示例3：

這里的時間復雜度為 O(1),因為傳進來的N并沒有使用；

2.冒泡排序時間復雜度

示例4：
這是一個冒泡排序，我們來求一下它的最好最壞和平均情況的時間復雜度。

• 最好：O(N)

• 最壞：O(N2)

• 平均：O(N)

這是一個經(jīng)過優(yōu)化后的冒泡排序，最好的情況就是該組數(shù)據(jù)已經(jīng)是有序的了，所以只需走一遍就好了，也是是O(N)。

而最壞的情況就把數(shù)組全部遍歷了一遍就是 N2；

我們前面說過平均情況就是我們個期望的情況，我們期望的當然就是O(N)。

3.二分查找的時間復雜度

我們知道求時間復雜度一般求的都是最壞的情況，二分查找只有當我們找最旁邊那兩個個數(shù)時才是最壞情況，我們就假設我們要找的就是最邊邊的那個數(shù)。

所以二分查找的時間復雜度為 O(log2N)。

4.遞歸的時間復雜度

• 遞歸的時間復雜度 = 遞歸的次數(shù)*每次遞歸執(zhí)行的操作的次數(shù)；

示例1：

這里的的遞歸次數(shù)為 N 次，這里沒有循環(huán)，每次執(zhí)行的是一個三目操作符相當于1次。所以為 N+1次，時間復雜度就是 O(N)。

示例2：
這是一個遞歸實現(xiàn)的斐波那契數(shù)列；

斐波那契數(shù)列的遞歸次數(shù)其實就是一個等比數(shù)列求和，最后的執(zhí)行次數(shù)為 (2n) - 1,通過通過推導大O階方法最后的時間復雜度為 O(2N)。

時間復雜度只是一個大概的，當數(shù)字足夠大時這里缺失的部分并不影響我們時間復雜度的計算。

三、空間復雜度

1.空間復雜度概念

空間復雜度是對一個算法在運行過程中臨時(額外)占用存儲空間大小的量度；

占用存儲空間大小的量度 。

空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數(shù)。

空間復雜度計算規(guī)則基本跟實踐復雜度類似，也使用大O漸進表示法。

2.空間復雜度的計算

(1) 冒泡排序

• 這個冒泡排序的空間復雜度為 O(1)；

為什么呢？因為空間復雜度是為了解決一個問題額外申請了其他變量，這里的array數(shù)組并不是額外的它是必須的，但這里的 sorted 是額外申請的，它每循環(huán)一次就定一次為什么不是O(N)呢？因為每循環(huán)一次這個變量是不是不要了呢？所以來來回回就是這一個變量。

(2) 斐波那契數(shù)列

這里的空間復雜度為 O(N)；
這里為了求第1~N的斐波那契數(shù)列的代碼，為了解決這個問題申請了一個額外的數(shù)組的空間，空間大小為 N+1。因為1是常數(shù)項，所以這個代碼的空間復雜度為 O(N)。

(3)遞歸

這是一個求階層的遞歸，他的空間復雜度為 O(N)；
因為遞歸在遞的過程中，每遞一次都會都會創(chuàng)建一個臨時變量。

小結(jié)

在計算機發(fā)展的早期，計算機的存儲容量很小，所以對空間復雜度很是在乎。但是經(jīng)過計算機行業(yè)的迅速發(fā)展，計算機的存儲容量已經(jīng)達到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關注一個算法的空間復雜度。因為現(xiàn)在的內(nèi)存不像以前那么貴，所以經(jīng)常聽到過犧牲空間來換取時間的說法。

到此，相信大家對“Java時間和空間的復雜度算法是什么”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關內(nèi)容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！