??專欄【數(shù)據(jù)結(jié)構(gòu)】
??喜歡的詩句：更喜岷山千里雪 三軍過后盡開顏。
??音樂分享【星辰大?！?/p>
大一同學(xué)小吉，歡迎并且感謝大家指出我的問題??
??
目錄
?時(shí)間復(fù)雜度分類
?? 方法
??平方階
??立方階
???對(duì)數(shù)階
??例子
?常數(shù)時(shí)間復(fù)雜度?O(1)
??數(shù)組讀取、索引和賦值
? ???判斷一個(gè)整數(shù)是否為偶數(shù)或奇數(shù)
?? 返回固定長(zhǎng)度的數(shù)組，字符串或其他數(shù)據(jù)結(jié)構(gòu)
?線性時(shí)間復(fù)雜度O(n)
??遍歷數(shù)組或列表中的元素
??線性搜索算法
???求數(shù)組或列表的元素之和或平均值
??對(duì)數(shù)時(shí)間復(fù)雜度O(log n)
??二分查找
??堆排序算法?
??平方時(shí)間復(fù)雜度O(n^2)
??冒泡排序
??插入排序算法
?立方時(shí)間復(fù)雜度
三重循環(huán)
?指數(shù)時(shí)間復(fù)雜度 O(2^n)
??斐波那契數(shù)列
???易錯(cuò)分析
?誤以為時(shí)間復(fù)雜度都要用 n 表示
??遞歸的時(shí)間復(fù)雜度
??數(shù)據(jù)規(guī)模的影響
?一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語句執(zhí)行時(shí)間的總和
一個(gè)語句的執(zhí)行時(shí)間為該條語句的重復(fù)執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積
?時(shí)間復(fù)雜度分類
?算法的時(shí)間復(fù)雜度是指運(yùn)行算法所需的時(shí)間與問題規(guī)模之間的增長(zhǎng)關(guān)系。通常用大O符號(hào)來表示算法的時(shí)間復(fù)雜度，也被稱為漸進(jìn)時(shí)間復(fù)雜度。算法時(shí)間復(fù)雜度分為以下幾類：
-
常數(shù)時(shí)間復(fù)雜度 O(1)：無論問題規(guī)模如何變化，算法的運(yùn)行時(shí)間都保持不變。
-
線性時(shí)間復(fù)雜度 O(n)：當(dāng)輸入規(guī)模n線性增加時(shí)，算法的運(yùn)行時(shí)間呈現(xiàn)出線性增長(zhǎng)趨勢(shì)。
-
對(duì)數(shù)時(shí)間復(fù)雜度 O(log n)：當(dāng)輸入規(guī)模n呈指數(shù)增長(zhǎng)時(shí)，算法的運(yùn)行時(shí)間呈對(duì)數(shù)增長(zhǎng)趨勢(shì)。
-
平方時(shí)間復(fù)雜度 O(n^2)：當(dāng)輸入規(guī)模n線性增加時(shí)，算法的運(yùn)行時(shí)間呈現(xiàn)出平方增長(zhǎng)趨勢(shì)。
-
立方時(shí)間復(fù)雜度O(n^3):當(dāng)輸入規(guī)模n線性增加時(shí)，算法的運(yùn)行時(shí)間呈現(xiàn)出立方增長(zhǎng)趨勢(shì)。
-
指數(shù)時(shí)間復(fù)雜度 O(2^n)：當(dāng)問題規(guī)模成指數(shù)增長(zhǎng)時(shí)，算法的運(yùn)行時(shí)間將會(huì)急劇增加。
在設(shè)計(jì)和優(yōu)化算法時(shí)，理解算法的時(shí)間復(fù)雜度非常重要。因?yàn)闀r(shí)間復(fù)雜度直接影響著算法的效率和可擴(kuò)展性，我們應(yīng)該盡可能選擇時(shí)間復(fù)雜度低的算法來解決問題。
?? 方法
找程序段里面頻度最大的語句
??平方階
1 x=0;y=0;
2 for(int i=1;i<=n;i++)
3?? ?x++;
4 for(int j=1;j<=n;j++)
5?? ?for(int k=1;k<=n;k++)
6?? ??? ?y++;
這個(gè)程序段里面頻度最大的語句是第6句，是n^2
??立方階
1 x=1;
2 for(int i=1;i<=n;i++)
3?? ?for(int j=1;j<=i;j++)
4?? ??? ?for(int k=1;k<=j;k++)
5?? ??? ??? ?x++;
?文章來源地址http://www.zghlxwxcb.cn/news/detail-419674.html
這個(gè)程序段里面頻度最大的語句是第5句，是n^3
???對(duì)數(shù)階
1 for(int i=1;i<=n;i*=2)
2 {
3?? ?x++;
4 }
?
??例子
?常數(shù)時(shí)間復(fù)雜度?O(1)
常數(shù)時(shí)間復(fù)雜度 O(1) 的算法指的是無論輸入規(guī)模如何變化，該算法的運(yùn)行時(shí)間都保持不變。這種算法的執(zhí)行時(shí)間與具體輸入的數(shù)據(jù)規(guī)模無關(guān)，通常是表格查找、數(shù)組索引或者直接返回常量值等簡(jiǎn)單的操作。?
??數(shù)組讀取、索引和賦值
int array[] = {1, 2, 3, 4, 5}; // 聲明一個(gè)數(shù)組
int x = array[2]; // 讀取數(shù)組中第三個(gè)元素，即3
array[3] = 10; // 修改數(shù)組中第四個(gè)元素，將其改為10
? ???判斷一個(gè)整數(shù)是否為偶數(shù)或奇數(shù)
int num = 7;
if (num % 2 == 0) {
? ? cout << num << " is even." << endl;
} else {
? ? cout << num << " is odd." << endl;
}
?? 返回固定長(zhǎng)度的數(shù)組，字符串或其他數(shù)據(jù)結(jié)構(gòu)
?
int* getFixedArray() {
? ? return new int[5]{1, 2, 3, 4, 5}; // 返回一個(gè)固定長(zhǎng)度的數(shù)組
}string getFixedString() {
? ? return "Hello, world!"; // 返回一個(gè)固定長(zhǎng)度的字符串
}
?
?線性時(shí)間復(fù)雜度O(n)
要從頭到尾遍歷一遍?
線性時(shí)間復(fù)雜度 O(n) 的算法指的是隨著輸入規(guī)模n的增長(zhǎng)，該算法的運(yùn)行時(shí)間呈現(xiàn)出線性增長(zhǎng)趨勢(shì)。也就是說，當(dāng)輸入規(guī)模n增加1倍時(shí)，算法的運(yùn)行時(shí)間也增加了1倍。通常情況下，O(n)的算法需要對(duì)數(shù)據(jù)進(jìn)行從頭到尾的遍歷處理。
??遍歷數(shù)組或列表中的元素
int array[] = {1, 3, 5, 7, 9};
for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
? ? cout << array[i] << " "; // 輸出數(shù)組中的每一個(gè)元素
}
以上代碼中，遍歷數(shù)組中的元素需要從頭到尾逐個(gè)訪問，時(shí)間復(fù)雜度為 O(n)。
??線性搜索算法
從數(shù)組或列表的開頭開始逐個(gè)比較元素的值，直到找到目標(biāo)元素或遍歷完整個(gè)數(shù)組或列表。
?bool linearSearch(int array[], int target) {
? ? for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
? ? ? ? if (array[i] == target) return true;
? ? }
? ? return false;
}
???求數(shù)組或列表的元素之和或平均值
?int sum(int array[]) {
? ? int result = 0;
? ? for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
? ? ? ? result += array[i];
? ? }
? ? return result;
}double average(int array[]) {
? ? return sum(array) / (double)(sizeof(array) / sizeof(array[0]));
}
??對(duì)數(shù)時(shí)間復(fù)雜度O(log n)
對(duì)數(shù)時(shí)間復(fù)雜度 O(log n) 的算法指的是隨著輸入規(guī)模n的增長(zhǎng)，該算法執(zhí)行時(shí)間呈現(xiàn)出對(duì)數(shù)增長(zhǎng)趨勢(shì)。例如，當(dāng)輸入規(guī)模n增加1倍時(shí)，算法的運(yùn)行時(shí)間可能會(huì)增加約2倍。常見的O(log n)算法通常是使用二分查找或者樹結(jié)構(gòu)等數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。
??二分查找
????????int binarySearch(int array[], int size, int target) {
? ? int left = 0;
? ? int right = size - 1;
? ? while (left <= right) {
? ? ? ? int mid = left + (right - left) / 2;
? ? ? ? if (array[mid] == target) return mid;
? ? ? ? else if (array[mid] < target) left = mid + 1;
? ? ? ? else right = mid - 1;
? ? }
? ? return -1;
}
以上代碼中，二分查找算法每次將元素范圍縮小一半，時(shí)間復(fù)雜度為 O(log n)?
??堆排序算法?
?
void heapify(int array[], int size, int i) {
? ? int largest = i;
? ? int left = 2 * i + 1;
? ? int right = 2 * i + 2;
? ? if (left < size && array[left] > array[largest]) largest = left;
? ? if (right < size && array[right] > array[largest]) largest = right;
? ? if (largest != i) {
? ? ? ? swap(array[i], array[largest]);
? ? ? ? heapify(array, size, largest);
? ? }
}void heapSort(int array[], int size) {
? ? for (int i = size / 2 - 1; i >= 0; i--) {
? ? ? ? heapify(array, size, i);
? ? }
? ? for (int i = size - 1; i > 0; i--) {
? ? ? ? swap(array[0], array[i]);
? ? ? ? heapify(array, i, 0);
? ? }
}?
以上代碼中，堆排序算法使用了二叉堆的數(shù)據(jù)結(jié)構(gòu)，每次都將元素拆分為兩個(gè)相等長(zhǎng)度的子集，并遞歸處理其中一個(gè)子集。因此，堆排序的時(shí)間復(fù)雜度為 O(log n)。在實(shí)現(xiàn)時(shí)，我們使用heapify()函數(shù)維護(hù)二叉堆的性質(zhì)，用兩個(gè)for循環(huán)來進(jìn)行堆排序。
??平方時(shí)間復(fù)雜度O(n^2)
平方時(shí)間復(fù)雜度 O(n^2) 的算法指的是隨著輸入規(guī)模n的增長(zhǎng)，該算法執(zhí)行時(shí)間呈現(xiàn)出平方增長(zhǎng)趨勢(shì)。例如，當(dāng)輸入規(guī)模n增加1倍時(shí)，算法的運(yùn)行時(shí)間會(huì)增加約4倍?
??冒泡排序
雙重for循環(huán)
?void bubbleSort(int array[], int size) {
? ? for (int i = 0; i < size - 1; i++) {
? ? ? ? for (int j = 0; j < size - i - 1; j++) {
? ? ? ? ? ? if (array[j] > array[j + 1]) swap(array[j], array[j + 1]);
? ? ? ? }
? ? }
}
以上代碼中，冒泡排序算法使用每一次內(nèi)層循環(huán)來比較相鄰元素的大小，并根據(jù)需要交換它們的位置，時(shí)間復(fù)雜度為 O(n^2)。在實(shí)現(xiàn)時(shí)，我們使用兩個(gè)for循環(huán)分別遍歷整個(gè)數(shù)組并比較相鄰的元素。
??插入排序算法
?void insertSort(int array[], int size) {
? ? for (int i = 1; i < size; i++) {
? ? ? ? int key = array[i];
? ? ? ? int j = i - 1;
? ? ? ? while (j >= 0 && array[j] > key) {
? ? ? ? ? ? array[j + 1] = array[j];
? ? ? ? ? ? j--;
? ? ? ? }
? ? ? ? array[j + 1] = key;
? ? }
}
?立方時(shí)間復(fù)雜度
三重循環(huán)
在這個(gè)例子中，我們使用了三重循環(huán)來演示立方階時(shí)間復(fù)雜度的算法，其中第一重循環(huán)運(yùn)行了 n 次，第二重循環(huán)也運(yùn)行了 n 次，第三重循環(huán)也運(yùn)行了 n 次，因此總的計(jì)算次數(shù)為 n * n * n，也就是立方階時(shí)間復(fù)雜度 O(n^3)。
#include <iostream>
using namespace std;
int main() {
? ? int n; // 輸入規(guī)模
? ? cin >> n;? ? for (int i = 0; i < n; i++) { // 第一重循環(huán)
? ? ? ? for (int j = 0; j < n; j++) { // 第二重循環(huán)
? ? ? ? ? ? for (int k = 0; k < n; k++) { // 第三重循環(huán)
? ? ? ? ? ? ? ? cout << i * j * k << " "; // 立方階計(jì)算
? ? ? ? ? ? }
? ? ? ? }
? ? }? ? return 0;
}
?在實(shí)際編程中，由于立方階算法的效率非常低下，通常應(yīng)該盡可能避免使用它，或者通過一些技巧將其轉(zhuǎn)化為更高效的算法，以提高程序的性能。
?指數(shù)時(shí)間復(fù)雜度 O(2^n)
指數(shù)時(shí)間復(fù)雜度是指算法執(zhí)行的時(shí)間與數(shù)據(jù)規(guī)模 n 的指數(shù)成正比，通常表示為 O(2^n)。一種計(jì)算方式是，在算法中使用了嵌套循環(huán)或遞歸，每次運(yùn)算次數(shù)都是上一次的兩倍或更多，這種情況就容易出現(xiàn)指數(shù)級(jí)別的時(shí)間復(fù)雜度。
??斐波那契數(shù)列
?#include <iostream>
using namespace std;int fib(int n) {
? ? if (n <= 1) {
? ? ? ? return n;
? ? } else {
? ? ? ? return fib(n - 1) + fib(n - 2);
? ? }
}int main() {
? ? int n = 10;
? ? for (int i = 0; i < n; i++) {
? ? ? ? int res = fib(i);
? ? ? ? cout << res << " ";
? ? }
? ? cout << endl;
? ? return 0;
}
???易錯(cuò)分析
?誤以為時(shí)間復(fù)雜度都要用 n 表示
這個(gè)例子，就用了 n 和?m 兩個(gè)字母
??遞歸的時(shí)間復(fù)雜度
遞歸算法在實(shí)現(xiàn)某些功能時(shí)非常方便，但是在計(jì)算時(shí)間復(fù)雜度時(shí)需要格外注意。因?yàn)檫f歸調(diào)用會(huì)導(dǎo)致函數(shù)的多次調(diào)用，從而增加程序的時(shí)間復(fù)雜度。
??數(shù)據(jù)規(guī)模的影響
算法的時(shí)間復(fù)雜度與數(shù)據(jù)規(guī)模有關(guān)，當(dāng)數(shù)據(jù)規(guī)模較小時(shí)，算法的時(shí)間復(fù)雜度可能看起來并不顯著，但是隨著數(shù)據(jù)規(guī)模的增大，算法的時(shí)間復(fù)雜度也會(huì)明顯增加。因此，在測(cè)試算法時(shí)間復(fù)雜度時(shí)，需要考慮不同數(shù)據(jù)規(guī)模下的運(yùn)行時(shí)間。
如果大家發(fā)現(xiàn)文章里面的問題和不明白的地方，歡迎提出自己的見解和疑問???
Code over!文章來源：http://www.zghlxwxcb.cn/news/detail-419674.html
?
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】時(shí)間復(fù)雜度(詳細(xì)解釋，例子分析，易錯(cuò)分析，圖文并茂)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
