一卓的博客

怕什么真理无穷，
进一寸有一寸的欢喜。

0%

算法时间复杂度的推导

发表于 阅读次数： Valine： 6.8k 6 分钟

大O表示法是最常用的表示算法时间复杂度的表示法。

本篇博客我们将推导各种算法的大O表示法。

示例1：查找前n个数字的总和。

在此示例中，我们必须找到前n个数字的总和。例如，如果n = 4，则输出应为1 + 2 + 3 + 4 =10。如果n = 5，则输出应为1 + 2 + 3 + 4 + 5 =15。让我们尝试各种解决方案此代码，然后尝试比较所有这些代码。

O（1）解决方案

1
2
3
4
int findSum(int n) 
{
    return n * (n+1) / 2; // 一条语句执行需要花费恒定的时间
}

在上面的代码中，只有一条语句，并且我们知道一条语句执行需要花费恒定的时间。基本思想是，如果该语句花费的时间恒定，则所有输入大小所花费的时间相同，我们将其表示为 O（1）。

O（n）解决方案

在此解决方案中，我们将运行从1到n的循环，并将这些值添加到名为“ sum”的变量中。

1
2
3
4
5
6
7
8
9
10
11
12
13
int findSum(int n) 
{
    int sum = 0; // -----------------> 需要花费恒定的时间 假设为 "c1"
    for(int i = 1; i <= n; ++i) // --> 在这里，i的创建将花费一定的恒定时间，而比较和增量将发生n次（c2 * n）
        sum = sum + i; // -----------> 这条语句将会被执行 n 次，假如本条语句花费的常量时间为 c3，则总时间为 c3*n
    return sum; // ------------------> 需要花费恒定的时间 假设为 "c4"
}
/*
* 总时间花费 = 所有语句花费的时间总和
* 在我们的这个例子中，有3条语句花费的都是常量时间。 例如： "sum = 0", "i = 0", 和 "return sum", 我们把所有的常量时间加起来，设其为 c
* 除此之外, 我们有两条语句将会执行 n 次。例如： "i < n(in real n+1)" and "sum = sum  + i" 总花费的时间为 c2*n + c3*n = c0*n
* 所以总的时间花费 = c0*n + c
*/

上面代码的大O表示法是O（c0 * n）+ O（c），其中 c 和 c0 是常数。因此，总时间复杂度可以写成 O（n）。

O（n²）解决方案

在此解决方案中，我们将求和变量“ i”的值增加一倍，即对于i = 1，求和变量将增加一次，即sum =1。对于i = 2，求和变量将被递增两次。因此，让我们看看解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
int findSum(int n) 
{
    int sum = 0; // ---------------------> 常量时间
    for(int i = 1; i <= n; ++i) 
        for(int j = 1; j <= i; ++j)
            sum++; // -------------------> 将会执行 [n * (n + 1) / 2]
    return sum; // ----------------------> 常量时间
}
/*
* 总时间 = 所有语句花费的时间总和
* 最多次执行的语句是 "sum++" 将会执行 n * (n + 1) / 2 次
* 所以，总的复杂度是: c1*n² + c2*n + c3 [c1 是 n² 的常数项, c2 是 n 的常数项, c3 是其他语句花费的常量时间]
*/

上面算法的大O符号是O（c1 *n²）+ O（c2 * n）+ O（c3）。

由于我们在大O中采用较高的增长顺序。因此，我们的表达式将简化为 O（n²）。

因此，到目前为止，我们已经针对同一问题看到了3种解决方案。现在，当你找到第一个“ n”个数字的总和时，你更喜欢使用哪种算法？

我们希望使用O（1）解决方案，因为该算法所花费的时间将是恒定的，而与输入大小无关。

示例2：搜索算法

在博客的这一部分中，我们将找到各种搜索算法（例如线性搜索和二分查找）的时间复杂度。

线性搜寻

在线性搜索中，我们将有一个数组，并且还给了一个元素。我们需要在数组中找到该元素的索引。例如，如果我们的数组是[8，10，3，2，9]，并且我们想找到位置“ 3”，那么我们的输出应该是2（基于0的索引）。以下是相同的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* @type of arr: integer array
* @type of n: integer(denoting size of arr)
* @type of k: integer(element to be searched)
*/
int linearSearch(int arr[], int n, int k)
{
    for(int i = 0; i < n; i++) 
        if(arr[i] == k)
            return i;
    return -1;
}
/*
* [说明]
* i = 0 ------------> 将会被执行1次
* i < n ------------> 将会被执行 n+1 次
* i++ --------------> 将会被执行 n 次
* if(arr[i] == k) --> 将会被执行 n 次
* return i ---------> 将会被执行1次(如果 "k" 在数组中)
* return -1 --------> 将会被执行1次(如果 "k" 不再数组中)
*/

线性搜索在最坏情况下的时间复杂度为 O（n），因为在最坏情况下，“ if（arr [i] == k） ”语句将执行“ n”次。

二分查找

在二分查找中，我们将拥有一个排序的数组，并将给出一个元素。我们必须找到该元素在数组中的位置。为此，我们遵循以下步骤：

  1. 通过找到数组的中间元素，将整个数组分为两部分。
  2. 查找中间元素是否等于要搜索的元素“ k”。如果相等，则返回该值。
  3. 如果中间元素不等于元素“ k”，则查找元素“ k”是否大于或小于中间元素。
  4. 如果元素“ k”大于中间元素，那么我们将在数组的[mid + 1至n]部分执行二分查找；如果元素“ k”小于中间元素，则我们将在数组的[0至mid-1]部分执行二分查找。
  5. 同样，我们将从步骤2开始重复。

让我们编写相同的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
* @type of arr: integer array
* @type of left: integer(left most index of arr)
* @type of right: integer(right most index of arr)
* @type of k: integer(element to be searched)
* @return type: integer(index of element k(if found), otherwise return -1)
*/
int binarySearch(int arr[], int left, int right, int k) 
{ 
    while (left <= right) { 
        // 查找中间元素
        int mid = left + (right - left) / 2; 
        // 判断 k 是否等于中间元素
        if (arr[mid] == k) 
            return mid; // 如果 k 等于中间元素，那么就返回下标
        // 如果 k 大于中间元素,忽略数组的左半部分
        if (arr[mid] < k) 
            left = mid + 1; // 更新左侧，右侧将保持不变
        // 如果 k 小于中间元素, 忽略数组的右半部分
        else
            right = mid - 1; // 更新右侧，左侧将保持不变
    } 
    // 如果没有找到，则返回 -1 
    return -1; 
}

二分查找算法的时间复杂度

  • 为了找到元素“ k”，假设在“第i次”迭代之后，二分查找的迭代停止，即数组的大小变为1。此外，每次迭代后，我们将数组的大小减小一半。
  • 因此，在第一次迭代中，数组的大小为“ n”，在第二次迭代中，数组的大小为“ n / 2”，在第三次迭代中，数组的大小为“（n / 2）/ 2 = n / 2²”，在第4次迭代中，数组的大小为“（（（n / 2）/ 2）/ 2 = n /2³”，依此类推。
  • 因此，在第 i 次迭代之后，数组的大小将为n / 2 ^ i。同样，在第 i 次迭代之后，数组的长度将变为1。因此，以下关系应成立：
1
2
3
4
5
=> n/2^i = 1
=> n = 2^i
=> log2 (n) = log2 (2^i)    [applying log2 both sides]
=> log2 (n) = i * log2 (2)  
=> i = log2 (n)             [as logn (n) = 1]

因此，二分查找算法的最坏情况时间复杂度是 log2（n）。

示例3：排序算法

在博客的这一部分中，我们将学习各种排序算法的时间复杂度。排序算法用于按升序或降序对给定数组进行排序。因此，让我们从选择排序开始。

选择排序

在选择排序中，在第一遍中，我们找到数组的最小元素并将其放在第一位。在第二遍中，我们找到数组的第二个最小元素并将其放在第二位，依此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* @type of arr: integer array
* @type of n: integer(length of arr)
*/
void selectionSort(int arr[], int n)  
{  
    // move from index 0 to n-1  
    for (int i = 0; i < n-1; i++)  
    {
        // finding the minimum element  
        int minIndex = i;  
        for (int j = i+1; j < n; j++)  
            if (arr[j] < arr[minIndex])  
                minIndex = j;  
        // Swap the found minimum element with the ith element  
        swap(arr[minIndex], arr[i]);  
    }  
}

选择排序的最坏情况时间复杂度是O（n²）。

冒泡排序

在冒泡排序中，我们比较相邻元素并将最小元素放在最大元素之前。例如，如果两个相邻元素为[4，1]，则最终输出将为[1，4]。

1
2
3
4
5
6
7
8
9
10
11
12
/*
* @type of arr: integer array
* @type of n: integer(length of arr)
*/
void bubbleSort(int arr[], int n)  
{  
    // move from index 0 to n-1
    for (int i = 0; i < n-1; i++)        
        for (int j = 0; j < n-i-1; j++)  
            if (arr[j] > arr[j+1])          // comparing adjacent elements
                swap(arr[j], arr[j+1]);   // swapping elements
}

冒泡排序的最坏情况时间复杂度是 O（n²）。

插入排序

在插入排序中，我们从第一个元素开始，然后检查该元素是否小于第0个元素。如果较小，则将其放在所需位置，否则检查第二个元素。如果第二个元素小于第0个元素或第一个元素，则将第二个元素放在所需的位置，依此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* @type of arr: integer array
* @type of n: integer(length of arr)
*/
void insertionSort(int arr[], int n)  
{  
    for (int i = 1; i < n; i++) 
    {  
        int key = arr[i];  // select value to be inserted
        int j = i - 1;     // position where number is to be inserted
        // check if previous no. is larger than value to be inserted
        while (j >= 0 && arr[j] > key) 
        {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        // changing the value
        arr[j + 1] = key;  
    }  
}

插入排序的最坏情况下时间复杂度为 O（n²）。

合并排序

合并排序使用分而治之技术（你将在本数据结构系列中了解有关分而治之的更多信息）。合并排序涉及以下步骤：

  • 通过找到中间元素，将数组分成两半。
  • 在上半部分和下半部分调用合并排序功能。
  • 现在，通过调用Merge函数合并两个部分。

在这里，我们将使用递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void merge(int* arr, int start, int mid, int end) 
{
	int temp[end - start + 1];        // creating temporary array
	int i = start, j = mid+1, k = 0;
	while(i <= mid && j <= end)       // traverse and add smaller of both elements in temp 
	{
		if(arr[i] <= arr[j]) 
		{
			temp[k] = arr[i];
			k += 1; i += 1;
		}
		else 
		{
			temp[k] = arr[j];
			k += 1; j += 1;
		}
	}
	// add the elements left in the 1st interval
	while(i <= mid) 
	{
		temp[k] = arr[i];
		k += 1; i += 1;
	}
	// add the elements left in the 2nd interval
	while(j <= end) 
	{
		temp[k] = arr[j];
		k += 1; j += 1;
	}
	// updating the original array to have the sorted elements
	for(i = start; i <= end; i += 1) 
	{
		arr[i] = temp[i - start]
	}
}


/*
* @type of arr: integer array
* @type of start: starting index of arr
* @type of end: eningd index of arr
*/
void mergeSort(int *arr, int start, int end) 
{
	if(start < end) 
	{
		int mid = (start + end) / 2; // finding middle element
		mergeSort(arr, start, mid);  // calling mergeSort for first half
		mergeSort(arr, mid+1, end);  // calling mergeSort for second half
		merge(arr, start, mid, end); // calling merge function to merge the arrays
	}
}

合并排序的最坏情况下的时间复杂度为 O（n log（n））。

下表显示了各种排序算法的最佳情况，平均情况和最坏情况的时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
-----------------------------------------------------------------------------
|Sorting Algorithm |    Best Case     |   Average Case   |    Worst Case    |
|------------------|------------------|------------------|------------------|
|Selection Sort    |       Ω(n²)      |      θ(n²)       |       O(n²)      |
|Bubble Sort       |       Ω(n)       |      θ(n²)       |       O(n²)      |
|Insertion Sort    |       Ω(n)       |      θ(n²)       |       O(n²)      |
|Merge Sort        |   Ω(n logn(n))   |   θ(n logn(n))   |   O(n logn(n))   |
|Quick Sort        |   Ω(n logn(n))   |   θ(n logn(n))   |       O(n²)      |
|Heap Sort         |   Ω(n logn(n))   |   θ(n logn(n))   |   O(n logn(n))   |
|Radix Sort        |      Ω(nk)       |      θ(nk)       |       O(nk)      |
|Bucket Sort       |     Ω(n + k)     |     θ(n + k)     |       O(n²)      |
-----------------------------------------------------------------------------

在此博客中，我们了解了算法的时间和空间复杂性。我们看到了如何使用这两个因素来分析算法的效率。因此，基本上，时间和空间之间需要权衡。希望本篇博客对你有所帮助。

原文链接: https://afteracademy.com/blog/time-and-space-complexity-analysis-of-algorithm

请作者喝杯咖啡吧