算法的時間復雜度(詳解)

前言:

算法(Algorithm):就是定義良好的計算過程,他取一個或一組的值為輸入,并產生出一個或一組值作為 輸出。簡單來說算法就是一系列的計算步驟,用來將輸入數據轉化成輸出結果

一、算法效率

1.1 如何衡量一個算法的好壞

如何衡量一個算法的好壞呢?比如對于以下斐波那契數列:

long long Fib(int N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}

斐波那契數列的遞歸實現方式非常簡潔,但簡潔一定好嗎?那該如何衡量其好與壞呢?

1.2 算法的復雜度

算法在編寫成可執行程序后,運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞,一般 是從時間和空間兩個維度來衡量的,即時間復雜度和空間復雜度。

時間復雜度主要衡量一個算法的運行快慢,而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發展的早期,計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經過計算機行業的迅速發展,計算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間復雜度。

復雜度在校招中的考察

常見復雜度對比

?

二、時間復雜度

2.1 時間復雜度的概念

時間復雜度的定義:在計算機科學中,算法的時間復雜度是一個函數,它定量描述了該算法的運行時間。一 個算法執行所耗費的時間,從理論上說,是不能算出來的,只有你把你的程序放在機器上跑起來,才能知道。但是我們需要每個算法都上機測試嗎?是可以都上機測試,但是這很麻煩,所以才有了時間復雜度這個 分析方式。一個算法所花費的時間與其中語句的執行次數成正比例,算法中的基本操作的執行次數,為算法的時間復雜度。

即:找到某條基本語句與問題規模N之間的數學表達式,就是算出了該算法的時間復雜度。

// 請計算一下Func1中++count語句總共執行了多少次?
void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

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

2.2 大O的漸進表示法

大O符號(Big O notation):是用于描述函數漸進行為的數學符號。

推導大O階方法:

1、用常數1取代運行時間中的所有加法常數。

2、在修改后的運行次數函數中,只保留最高階項。

3、如果最高階項存在且不是1,則去除與這個項目相乘的常數。得到的結果就是大O階。

使用大O的漸進表示法以后,Func1的時間復雜度為:

O(N^2)

N = 10 F(N) = 100

N = 100 F(N) = 10000

N = 1000 F(N) = 1000000

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項,簡潔明了的表示出了執行次數。

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

最壞情況:任意輸入規模的最大運行次數(上界)

平均情況:任意輸入規模的期望運行次數

最好情況:任意輸入規模的最小運行次數(下界)

例如:在一個長度為N數組中搜索一個數據x

最好情況:1次找到

最壞情況:N次找到

平均情況:N/2次找到

在實際中一般情況關注的是算法的最壞運行情況,所以數組中搜索數據時間復雜度為O(N)

三、常見時間復雜度計算舉例

實例1:

// 計算Func2的時間復雜度?
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

基本操作執行了2N+10次,通過推導大O階方法知道,時間復雜度為 O(N)

實例2:

// 計算Func3的時間復雜度?
void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++k){++count;}for (int k = 0; k < N; ++k){++count;}printf("%d\n", count);
}

基本操作執行了M+N次,有兩個未知數M和N,時間復雜度為 O(N+M)

實例3:

// 計算Func4的時間復雜度?
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

基本操作執行了100次,通過推導大O階方法,時間復雜度為 O(1)

注:O(1)代表常數次

實例4:

// 計算strchr的時間復雜度?
const char * strchr ( const char * str, int character );

我們分析一下

while (*str)
{if (*str == charcter)return str;else++str;
}

基本操作執行最好1次,最壞N次,時間復雜度一般看最壞,時間復雜度為 O(N)

實例5:?

// 計算BubbleSort的時間復雜度?
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

基本操作執行最好N次,最壞執行了N*(N-1)/2次,通過推導大O階方法+時間復雜度一般看最壞,時間復雜度為 O(N^2)

實例6:

// 計算BinarySearch的時間復雜度?
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;// [begin, end]:begin和end是左閉右閉區間,因此有=號while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid - 1;elsereturn mid;}return -1;
}

分析二分查找的時間復雜度:?

查找區間的變化:

N
N/2?
N/4
N/8
……?

1

二分查找什么情況下最壞?查找區間只剩一個數,或者找不到,也就是:N/2/2…/2 = 1

查找了多少次,就是除了多少個2,假設查找了x次 2^x = N

那么查找次數為:x=logN(底數忽略不寫)

則時間復雜度: O(logN)

因為寫的時候需要支持專業公式,否則不好寫底數,時間復雜度當中,為了方便,logN可以省略底數直接寫成logN,其他底層不能省略(其他底數也很少出現)

實例7:

// 計算階乘遞歸Fac的時間復雜度?
long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}

遞歸時間復雜度:所有遞歸調用次數累加(等差數列)?

通過計算分析發現基本操作遞歸了N次,時間復雜度為O(N)。

實例8:

// 計算斐波那契遞歸Fib的時間復雜度?
long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}

如下圖所示:每次遞歸都是以2倍的形式增長,累加求和,我們可以使用等比數列錯位相減法

??

計算分析發現基本操作遞歸了2^N次,時間復雜度為O(2^N)。

這種算法基本上是廢了,只有理論意義,實踐中太慢了。?

四、復雜度的OJ練習

1.消失的數字

OJ鏈接:消失的數字

?

思路一:先排序,再依次查找,如果下一個值不等于前一個+1,下一個值就是消失數字,如果我們使用冒泡排序進行排序,就不符合題目要求了,因為它的時間復雜度是O(N^2)

思路二:求和0到N,再依次減去數組中的值,剩下的那個值就是消失數字,累加的時間復雜度為O(N),如果N的數字比較大可能會導致棧溢出。

代碼如下:

思路三:我們可以使用異或,把數組中0到N的元素全部異或起來,相同為0相異為1,最后那個數字就是消失的數字,這樣還可以防止棧溢出

代碼如下:

int missingNumber(int* nums, int numsSize)
{int x = 0;int N = numsSize;for(int i = 0;i<numsSize;i++){x^=nums[i];}for(int j = 0;j<=numsSize;j++){x^=j;}return x;
}

2.輪轉數組

?OJ鏈接:輪轉數組

思路一:先寫出旋轉一次的函數,在調用k次,k的真實旋轉次數為k%=numsSize

代碼如下:

但是超出時間限制了

我們分析一下:

最壞情況 :k%N等于N-1 ->?O(N^2)

最好情況:k%N等于0

時間復雜度為O(N^2)

思路二:我們使用三段逆置,我們先讓前n-k個逆置一下,然后再把后k個逆置一下,最后整體逆置。

代碼如下:

void reverse(int*a,int left,int raght)
{while(left < raght){int temp = a[left];a[left] = a[raght];a[raght] = temp;++left;--raght;}
}
void rotate(int* nums, int numsSize, int k) 
{k %= numsSize;reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);
}

時間復雜度為O(N),我們也可以使用memcpy


總結

時間復雜度是衡量算法執行效率的重要指標,它表示算法隨輸入數據規模增長時執行時間的變化趨勢。優化時間復雜度可以節省計算資源、提高系統性能、滿足實時性要求,并提升用戶體驗。在設計算法時,應充分考慮時間復雜度的優化,以實現高效、穩定的性能表現。?

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

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

相關文章

3.Linux系統環境搭建

一、虛擬化機&#xff1a;指的是通過虛擬化技術將一臺計算機分為多臺邏輯計算機。注&#xff1a;虛擬機共用CPU和內存資源。 二、虛擬機用途&#xff1a; 1.搭建學習環境&#xff1a;例如在同一間實驗室里&#xff0c;物理機Windows系統&#xff0c;虛擬機可以用Linux系統。 …

匯舟問卷:國外問卷調一天900

大家好&#xff0c;我是匯舟問卷&#xff0c;專注于國外問卷調查互聯網項目。夏天已經來臨&#xff0c;您是否在三伏天頂著大太陽上班&#xff0c;汗水浸濕了衣襟&#xff0c;卻依然要面對繁瑣的工作和無盡的壓力&#xff1f; 在這個炎熱的季節里&#xff0c;我們都渴望找到一…

什么是React?

01 Why React? What is React? I think the one-line description of React on its home page (https://react.dev/) is concise and accurate: “A JavaScript library for building user interfaces.” 我認為React主頁(https://react.dev/)上的一行描述既簡潔又準確: …

ch3運輸層--計算機網絡期末復習(持續更新中)

運輸層位于網絡層之上 運輸層協議提供的某些服務受到網絡層協議的限制。比如,時限和帶寬保證。 運輸層也提供自己的特殊服務。比如,可靠數據傳輸服務,安全性服務。 網絡層:兩個主機之間的邏輯通信 運輸層:兩個進程之間的邏輯通信 網絡地址:主機的標識(IP地址) 傳輸地址: …

vmware中Ubuntu虛擬機和本地電腦Win10互相ping通

初始狀態 使用vmware17版本安裝的Ubuntu的20版本&#xff0c;安裝之后什么配置都要不懂&#xff0c;然后進行下述配置。 初始的時候是NAT&#xff0c;沒動的. 設置 點擊右鍵編輯“屬性” 常規選擇“啟用”&#xff1a; 高級選擇全部&#xff1a; 打開網絡配置&#xff0c;右鍵屬…

玄機平臺應急響應—Linux入侵排查

1、前言 這篇文章主要說一下linux的入侵排查&#xff0c;也就是說當你的服務器已經被入侵的時候&#xff0c;該如何去排查使其恢復正常。下面是排查的步驟&#xff0c;但是實際情況往往更為復雜&#xff0c;需要進一步來分析&#xff0c;而不是無腦的按照步驟來敲就完事了。 …

HAL庫使用FreeRTOS實時操作系統時配置時基源(TimeBase Source)

需要另外的定時器&#xff0c;用systic的時候生成項目會有警告 https://blog.51cto.com/u_16213579/10967728

同比和環比

1、概述 同比和環比是兩種常見的數據分析方法&#xff0c;用于衡量數據在不同時間段的變化情況。通過同比和環比的計算&#xff0c;可以更清晰地了解數據在不同時間段的增長或下降情況&#xff0c;從而為決策提供依據。 2、同比 同比&#xff08;Year-on-Year, YoY&#xff09…

05-28 周二 TTFT, ITL, TGS 計算過程以及LLama2推理代碼調試過程

05-28 周二 LLama2推理代碼調試過程 時間版本修改人描述2024年5月28日15:03:49V0.1宋全恒新建文檔 簡介 本文主要用于求解大模型推理過程中的幾個指標&#xff1a; 主要是TTFT&#xff0c;ITL&#xff0c; TGS 代碼片段 import osdata_dir "/workspace/models/" m…

獲取 Excel 單元格的條件格式是否成立及其改變后的屬性(如背景顏色)

獲取 Excel 單元格的條件格式是否成立及其改變后的屬性&#xff08;如背景顏色&#xff09;&#xff0c;直接通過 VSTO API 是有挑戰的&#xff0c;因為條件格式的實際應用效果在 Excel 的內部邏輯中&#xff0c;并不直接暴露給外部 API。盡管如此&#xff0c;可以通過一些工作…

unity中的常用屬性修飾符

unity中的常用屬性修飾符 一、前言二、常用修飾符三、結語 一、前言 在做unity開發編輯腳本的時候經常會用到屬性修飾符&#xff0c;使開發調試更加便捷。初學者見過最多的莫過于[Header("標題文本")]了吧&#xff0c;除此之外其實還有很多&#xff0c;這篇文章列舉說…

MFC工控項目實例一主菜單制作

1、本項目用在WIN10下安裝的vc6.0兼容版實現。創建項目名為SEAL_PRESSURE的MFC對話框。在項目res文件下添加相關256色ico格式圖片。 2、項目名稱&#xff1a;密封壓力試驗機 主菜單名稱&#xff1a; 系統參數 SYS_DATA 系統測試 SYS_TEST 選擇型號 TYP_CHOICE 開始試驗 TES_STA…

sdbusplus:通過文件描述符傳遞數據

有的時候需要傳遞大量的數據,如果將數據通過dbus傳遞,會消耗大量的帶寬。可以通過傳遞一個文件描述符替代傳遞數據: 以下的service通過文件描述符接收數據: //fd_service.cpp #include <sdbusplus/asio/connection.hpp> #include <sdbusplus/asio/object_server…

U盤無法打開?數據恢復與預防措施全解析

在日常生活和工作中&#xff0c;U盤已成為我們存儲和傳輸數據的重要工具。然而&#xff0c;有時我們會遇到U盤無法打開的情況&#xff0c;這無疑給我們帶來了諸多不便。本文將深入探討U盤打不開的現象、原因及解決方案&#xff0c;并分享如何預防此類問題的發生。 一、U盤無法訪…

Java實現對象存儲的4種方式(本地對象存儲、MINIO、阿里云OSS、FastDFS)

文章目錄 Java實現對象存儲的3中方式1、概述2、本地對象存儲2.1 配置本地文件相關信息2.2 通用映射配置 ResourcesConfig2.3 文件上傳業務 LocalSysFileServiceImpl2.4 上傳接口2.5 演示 3、MINIO3.1 依賴3.2 配置3.3 配置連接信息3.4. MINIO文件上傳業務3.5 文件上傳下載接口3…

學生管理系統 面向對象

創建一個實例對象后 把實例對象添加到列表后 每次遍歷列表 都能獲得一個實例對象 然后就可以使用實例對象的屬性和方法了 學生管理系統 面向對象 兩個類 學生管理類 學生類 # 學生類 # 屬性 姓名 電話 class Student:def __init__(self, name, phone):self.name nameself.phon…

各大翻譯軟件代碼——潯川AI翻譯研發社團

一、前言 有道翻譯API&#xff08;主要推薦&#xff09; 百度翻譯API&#xff08;需要申請key與密鑰&#xff0c;每月100萬免費字符&#xff09; 谷歌翻譯API&#xff08;需要梯子&#xff0c;而且不穩定&#xff0c;不推薦&#xff09; 二、代碼 1、有道翻譯 def is_Chi…

高性價比、超強功能的開源工單解決方案

在企業日常運營中&#xff0c;工單管理系統是不可或缺的工具。高效的工單管理不僅能提升工作效率&#xff0c;還能顯著提高客戶滿意度。今天&#xff0c;我們為您推薦搭貝工單派單系統——一款超高性價比、功能齊全的開源工單管理系統。 &#x1f50d; 為什么選擇搭貝工單派單…

LangChain入門開發教程(一):Model I/O

官方文檔&#xff1a;https://python.langchain.com/docs/get_started/introduction/ LangChain是一個能夠利用大語言模型&#xff08;LLM&#xff0c;Large Language Model&#xff09;能力進行快速應用開發的框架&#xff1a; 高度抽象的組件&#xff0c;可以像搭積木一樣&a…

Nginx R31 doc-17-debugging 調試

前言 大家好&#xff0c;我是老馬。很高興遇到你。 我們為 java 開發者實現了 java 版本的 nginx https://github.com/houbb/nginx4j 如果你想知道 servlet 如何處理的&#xff0c;可以參考我的另一個項目&#xff1a; 手寫從零實現簡易版 tomcat minicat 手寫 nginx 系列 …