快捷導(dǎo)航

Java基礎(chǔ)之toString的序列化匿名對(duì)象復(fù)雜度精解

更新時(shí)間：2021年09月26日 15:55:24 作者：愛內(nèi)卷的王同學(xué)

序列化即為把內(nèi)存中的對(duì)象轉(zhuǎn)換為字節(jié)寫入文件或通過網(wǎng)絡(luò)傳輸?shù)竭h(yuǎn)端服務(wù)器，本章節(jié)將帶你了解Java toString的序列化匿名對(duì)象復(fù)雜度，需要的朋友可以參考下

序列化

toString 方法的原理就是序列化，他可以幫助我們講一個(gè)抽象的對(duì)象變得具體，譬如把對(duì)象里面的名字、年齡、身高等信息具象為字符串。（總之，序列化：將對(duì)象轉(zhuǎn)化為字符串；反序列化：將字符串轉(zhuǎn)化為對(duì)象）。

匿名對(duì)象

匿名對(duì)象適用于只想使用一次的情況，因?yàn)槟涿麑?duì)象是沒有引用的，每次用都要重新new 一遍對(duì)象，很麻煩。

class Person {
    public void eat{
        //略
    }
    public void show{
        //內(nèi)容略
    }
}
//主函數(shù)略寫
new Person.eat();//此即為匿名函數(shù)的寫法
new Person.show();

復(fù)雜度

復(fù)雜度是衡量一個(gè)計(jì)算機(jī)運(yùn)行效率的東西，分為時(shí)間復(fù)雜度和空間復(fù)雜度，空間復(fù)雜度衡量的是一個(gè)程序所占用儲(chǔ)存空間，時(shí)間復(fù)雜度衡量的是一個(gè)程序的運(yùn)行時(shí)間（當(dāng)然，不是那種真實(shí)的時(shí)間），但是當(dāng)下，計(jì)算機(jī)的內(nèi)存空間已經(jīng)發(fā)展到了一定的高度，所以不需要再去關(guān)注這個(gè)東西了。

時(shí)間復(fù)雜度

我們是不可能能真正去測(cè)算一個(gè)程序的執(zhí)行時(shí)間的，因?yàn)?，每個(gè)計(jì)算機(jī)的性能不同，執(zhí)行的時(shí)間快慢也不同。一個(gè)算法所花費(fèi)的時(shí)間是正比于語(yǔ)句的執(zhí)行次數(shù)的。

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

以下為時(shí)間復(fù)雜度示例，一起來(lái)具體分析。

上面已經(jīng)講過了，時(shí)間復(fù)雜度的定義就是算法中的基本操作的執(zhí)行次數(shù)，所以我們算一下上面這段代碼每段語(yǔ)句的執(zhí)行次數(shù)就可以求出（上面的圖片已經(jīng)標(biāo)注），所以這段代碼的時(shí)間復(fù)雜度為：N^2 + 2N + 10。（1 太小，可以忽略）。

大O的漸進(jìn)表示法

用參數(shù) 1 取代式子中的常數(shù)項(xiàng)在修改后函數(shù)中只保留最高項(xiàng)如果最高項(xiàng)的系數(shù)不為 1 ，那么就把他前面的系數(shù)去掉

（其實(shí)歸根到底就是，對(duì)于一個(gè)有不同項(xiàng)的式子（譬如：N^2+2N+10 變 N^2），去掉最高項(xiàng)以外的其他項(xiàng) ，去掉最高項(xiàng)的常數(shù)，但是如果其時(shí)間復(fù)雜度僅僅是一個(gè)常數(shù)，直接轉(zhuǎn)為O（1）即可）

時(shí)間復(fù)雜度的分類

時(shí)間復(fù)雜度被分為三類（可以以數(shù)組的查找為例）

第一類：最好情況（1次找到，即假定我們要找的是數(shù)組的第一個(gè)元素）

第二類：最壞情況（最后一個(gè)找到，即假設(shè)我們要找的是數(shù)組的最后一個(gè)元素，N次）

第三類：平均情況（中間找到，即假設(shè)我們要找到的是數(shù)組的中間元素，N/2次）

但是，平時(shí)我們嘴里面常說(shuō)的時(shí)間復(fù)雜度其實(shí)是最壞的情況，所以，以上以查找數(shù)組為例的時(shí)間復(fù)雜度應(yīng)該為：O（N）。

計(jì)算時(shí)間復(fù)雜度的方法

既要看程序的執(zhí)行次數(shù)，也要看程序的具體的執(zhí)行內(nèi)容而定。

示例 1

如上圖，要求計(jì)算冒泡排序的時(shí)間復(fù)雜度。這里要算出最好情況和最壞情況，最好情況也就是順序，一次性的只有圖中的第一個(gè)框子的程序進(jìn)行執(zhí)行，第二個(gè)框子里的程序根本沒執(zhí)行所以不納入考慮范圍。因此，最好情況為：O(N)。

但是最壞情況就是逆序，從大到小的那種，這樣的話，第二個(gè)框子必須每次都執(zhí)行。即為：N(N-1)，因此根據(jù)剛剛上面的規(guī)則，去掉最高項(xiàng)以外的其他項(xiàng)之后，最壞情況為：O(N^2)。

示例 2

如上圖，是二分查找的代碼，這個(gè)代碼要計(jì)算它的時(shí)間復(fù)雜度，就必須知道里面循環(huán)執(zhí)行的次數(shù)，而下圖，以四個(gè)元素的數(shù)組為例進(jìn)行查找，最終發(fā)現(xiàn)規(guī)律（注意，這里要算的時(shí)間復(fù)雜度考慮最壞情況，也就是說(shuō)我們不管數(shù)組里有幾個(gè)元素查找的都是最后一個(gè)元素）。如圖，分支處的判斷與賦值其實(shí)就是進(jìn)入循環(huán)里面所做的事情，也就是說(shuō)有幾個(gè)分支，循環(huán)就執(zhí)行了幾次，下圖那個(gè)，四個(gè)元素，三個(gè)分支，所以，循環(huán)執(zhí)行了三次，其時(shí)間復(fù)雜度也是 3 。最后的到用n 表示出來(lái)的n ，但是下圖中的值其實(shí)并不準(zhǔn)確，根據(jù)上面說(shuō)過的原理，我們可以略去 1 那個(gè)常數(shù)。然后log 里面的 2 也是能夠去掉的，用 log n 特指二分查找的時(shí)間復(fù)雜度。

示例3

計(jì)算遞歸的時(shí)間復(fù)雜度，公式：時(shí)間復(fù)雜度 = 遞歸的次數(shù) * 遞歸執(zhí)行的次數(shù)。

//階乘遞歸
long factorial(int n) {
    return n < 2 ? n :factorial(n-1)*n;
}//求此段代碼的時(shí)間復(fù)雜度
//  n     a
//  2     2*1
//  3     3*1
//綜上，找出的規(guī)律說(shuō)明輸入多少
//時(shí)間復(fù)雜度就是多少。
//因此，答案為O(N)

//計(jì)算斐波那契數(shù)列的時(shí)間復(fù)雜度
int fibonacci(int n) {
    return n < 2 ? n :fibonacci(n-1)+fibonacci(n-2);
}
//

空間復(fù)雜度

空間復(fù)雜度不是看程序占多少字節(jié)，這個(gè)是沒有意義的，但是如果我們要計(jì)算空間復(fù)雜度的話，其實(shí)求的是變量的個(gè)數(shù)。

如上圖，冒泡排序的空間復(fù)雜度是O(1)，之所以是這樣子的是因?yàn)楹瘮?shù)參數(shù)里面的那個(gè) int[] array，他其實(shí)并不算在內(nèi)，因?yàn)檫@是一個(gè)必須空間，就是說(shuō)，要存這N 個(gè)數(shù)據(jù)就必須是要開辟的，這種必須空間不納入考慮范圍。但是循環(huán)里面的那個(gè) sort 變量是納入考慮范圍，因?yàn)檫@才是實(shí)實(shí)在在創(chuàng)建的變量，又因?yàn)檫@個(gè)變量在for 循環(huán)里面，僅僅是每次循環(huán)賦一次值，并不是每次循環(huán)都創(chuàng)建一次，所以時(shí)間復(fù)雜度為 1。