bl双性强迫侵犯h_国产在线观看人成激情视频_蜜芽188_被诱拐的少孩全彩啪啪漫画

第二章：C語言數據結構與算法初階之復雜度-創新互聯

系列文章目錄

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：域名注冊、虛擬主機、營銷軟件、網站建設、金沙網站維護、網站推廣。文章目錄
  • 系列文章目錄
  • 前言
  • 一、復雜度
  • 二、時間復雜度
    • (1) 定義
    • (2) 大O的漸進表示法
      • 例子
  • 三、空間復雜度
      • 例子
  • 四、常見復雜度對比
  • 五、復雜度的oj練習
  • 總結

前言

如何衡量一個算法的好壞呢？我們一般用復雜度來形容。

一、復雜度

算法在編寫成可執行程序后，運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。
時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經過計算機行業的迅速發展，計算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間復雜度。

二、時間復雜度

時間復雜度算的不是一個程序在某臺機器上跑的時間，因為每個機器運算速率不一樣，所以要脫離運行環境來考量算法。

(1) 定義

時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數，這里的函數是數學中帶未知數函數式，它定量描述了該算法的運行時間。

一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數，為算法
的時間復雜度。

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

//F(N) = N * N + 2 * N + 10
(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)

例子
void Func2(int N)
{int count = 0;
    for (int k = 0; k< 2 * N ; ++ k)
    {++count;
    }
 	// 2 * N
    int M = 10;
    while (M--)
    {++count;
    }
    // 10
 
    printf("%d\n", count);
}

	//Fun2(N) = 2 * N + 10；
	//時間復雜度為O(N);
// 計算Func3的時間復雜度？
void Func3(int N, int M)
{int count = 0;
    for (int k = 0; k< M; ++ k)
    {++count;
    }
 	//M
    for (int k = 0; k< N ; ++ k)
    {++count;
    }
    //N
    printf("%d\n", count);
    
}
	//Funce(N,M) = N + M;
    //時間復雜度為O(N + M);
// 計算Func4的時間復雜度？
void Func4(int N)
{int count = 0;
    for (int k = 0; k< 100; ++ k)
    {++count;
    }
    // 100
    printf("%d\n", count);
}
	//Func4(N) = 100;
	//時間復雜度為O(1); O(1) -- 代表常數次，因為現在計算機計算速度很快，一百次和一億次一樣快
// 計算strchr的時間復雜度？
const char * strchr ( const char * str, int character );
//strchr查找字符串中是否有*str,有的話返回該字符。
//strchar() = 最好:1 最壞:N 平均: (1+N)/2
//時間復雜度為O(N)
// 計算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;
    }
}
// BubbleSort() = 最壞:(N - 1) + (N - 2) + ... + 1 = N * N / 2
//時間復雜度為O(N*N)
// 計算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;
        else
            return mid;
    }
 
    return -1;
}
//BinarySearch() = N/2/2/2.../2 = 1 每次查找，查找區間縮小一半，查抄多少次，就是除以2多少次，直到區間為1個元素，假設查找x次，N = 1 * 2 * 2 * ... * 2, N = 2^x, x = log(2)N
//時間復雜度為O(logN) (2)可以省略
// 計算階乘遞歸Fac的時間復雜度？
long long Fac(size_t N)
{if(0 == N)
        return 1;
    
    return Fac(N-1)*N;
}
//Fac() =  N; 
//時間復雜度為O(N);
long long Fac(size_t N)
{if(0 == N)
        return 1;
    for(size_t i = 0;i< N;++i){//...
    }
    return Fac(N-1)*N;
}
//Fac() = N + (N-1) + (N-2) + ... + 1;
//時間復雜度O(N*N)
//遞歸時間復雜度:每次遞歸調用的執行次數累加

在這里插入圖片描述

// 計算斐波那契遞歸Fib的時間復雜度？
long long Fib(size_t N)
{if(N< 3)
        return 1;
    
    return Fib(N-1) + Fib(N-2);
}
// Fib() = 2 * 2 * 2 * 2 * ... * 2 
// 時間復雜度為O(2^N);
// 空間復雜度O(N) 時間是一去不復返，空間是可以重復利用的
三、空間復雜度

空間復雜度也是一個數學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度 。
空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數。空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法。
注意：函數運行時所需要的棧空間(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運行時候顯式申請的額外空間來確定。

例子
//計算Func4空間復雜度
void Func4(int N)
{int count = 0;
    for (int k = 0; k< 100; ++ k)
    {++count;
    }
    printf("%d\n", count);
}
//Func4 = 2
//空間復雜度為O(1)
// 計算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;
    }
}
// BubbleSort() = 3
// 空間復雜度為O(1)
// 計算Fibonacci的空間復雜度？
// 返回斐波那契數列的前n項
long long* Fibonacci(size_t n)
{if(n==0)
         return NULL;
    
    long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i<= n ; ++i)
    {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
 
    return fibArray;
}
//Fibonacci() = n+1
//空間復雜度為O(n)
// 計算斐波那契遞歸Fib的時間復雜度？
long long Fib(size_t N)
{if(N< 3)
        return 1;
    
    return Fib(N-1) + Fib(N-2);
}
// Fib() = N
// 空間復雜度為O(N) 時間是一去不復返，空間是可以重復利用的

在這里插入圖片描述

// 計算階乘遞歸Fac的空間復雜度？
long long Fac(size_t N)
{if(N == 0)
        return 1;
    
    return Fac(N-1)*N;
}
// Fac() = N
//空間復雜度為O(N)
//遞歸空間復雜度：每次遞歸調用的變量個數累加
四、常見復雜度對比

在這里插入圖片描述

五、復雜度的oj練習

題目1

數組nums包含從0到n的所有整數，但其中缺了一個。請編寫代碼找出那個缺失的整數。你有辦法在O(n)時間內完成嗎？

注意：本題相對書上原題稍作改動

示例 1：

輸入：[3,0,1]
輸出：2

思路

//思路1
求和相減
(n + 1) * n / 2 - (數組的總和）
時間復雜度:O(N)
空間復雜度:O(1)

//思路2
qort排序
時間復雜度:O((logN) * N) (快排）
空間復雜度:O(logN)(快排)

//思路3
異或
時間復雜度：O(N)
空間復雜度：O(1)

題目2

給你一個數組，將數組中的元素向右輪轉 k 個位置，其中 k 是非負數。

 

示例 1:

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉 1 步: [7,1,2,3,4,5,6]
向右輪轉 2 步: [6,7,1,2,3,4,5]
向右輪轉 3 步: [5,6,7,1,2,3,4]

思路

思路1
三段逆置法
//將0到n-k-1逆置
//將n-k到numsSize-1逆置
//將0到numsSize-1逆置
時間復雜度：O(N)
空間復雜度：O(1)

思路2
將末尾元素移動到首元素，其余元素整體后移
時間復雜度：O(N * N)
空間復雜度：O(1)

思路3
將第k+1元素及其后面的元素拷貝到另一數組前面，再將第0個到第k個元素拷貝到數組后面
時間復雜度：O(N)
空間復雜度：O(N)
總結

時間復雜度是基本操作次數的量度，空間復雜度是額外申請的變量總個數的量度

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站欄目：第二章：C語言數據結構與算法初階之復雜度-創新互聯
鏈接URL：http://vcdvsql.cn/article36/cseopg.html

成都網站建設公司_創新互聯，為您提供微信小程序、全網營銷推廣、電子商務、關鍵詞優化、品牌網站設計、移動網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯

商城網站建設