【数据结构】时间复杂度

大家好，欢迎来到IT知识分享网。

目录

一、时间复杂度的概念

二、大O的渐进表示法

三、常见时间复杂度计算举例

四、时间复杂度相关题目

一、时间复杂度的概念

       在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一 个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知 道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法 的时间复杂度

// 请计算一下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); }

Func1被执行的次数：

• N = 10        F(N) = 130
• N= 100       F(N) = 10210
• N = 1000    F(N) =

            实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这 里我们使用大O的渐进表示法。

二、大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

还有一些算法的时间复杂度存在最好，平均，最差三种情况：例如在一个长度为N数组中查找数据

最好的情况就是1次找到，平均情况是N/2，最差情况是N。

• 最坏情况：任意输入规模的最大运行次数(上界)
• 平均情况：任意输入规模的期望运行次数
• 最好情况：任意输入规模的最小运行次数(下界)

那么（一）中的Func1函数，使用大O的渐进表示法后时间复杂度为：

 在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为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); } 

Func2的时间复杂度为：F(N) = 2*N + 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); } 

Func3的时间复杂度为：F(N) = M+N

使用大O的渐进表示法后时间复杂度为：O(M+N)

例3.

// 计算Func4的时间复杂度？ void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count); }

Func4的时间复杂度为：F(N) = 100

使用大O的渐进表示法后用１代表常数，所以时间复杂度为：O(1)

例4.

// 计算strchr的时间复杂度？ const char * strchr ( const char * str, int character ) while(*str) { if(*str==character) return str; str++; }

Func3的时间复杂度为：F(N) = N

使用大O的渐进表示法后时间复杂度为：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; } }

这是在原本的冒泡排序上进行了优化，如果在一整趟排序中没有进行交换，那么将会跳出循环。

BubbleSort的时间复杂度是：F(N) = (n-1) + (n-2) +……+ 2 + 1

用等差数列公式整合后：N * (N-1) / 2

使用大O的渐进表示法后时间复杂度为：

例6.

// 计算BinarySearch的时间复杂度？ int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n-1; while (begin < end) { int mid = begin + ((end-begin)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid; else return mid; } return -1; } 

BinarySearch的时间复杂度函数为F(N) = N / 2 / 2 / 2 … /2 = 1

使用大O渐近表示法：O(log₂N)或O(logN) — > x：N / 2^x = 1 -> N = 2^x -> log₂N = x

例7.

// 计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; } 

例8.

// 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); } 

2^0 + 2^1 + 2^2 + 2^3 … +2^(N-3) + 2^(N-2)+ 2^(N-1)=等比数列-缺少常数 

使用大O的渐进表示法后时间复杂度为：O(2^N)

 常见复杂度对比

四、时间复杂度相关题目

1.消失的数字

         消失的数字

        题述：数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

  方法1.

        首先进行排序，使用qsort排序后，再遍历一遍数组，看数组中数据与前一项数据之差是否为1，若不是则返回

int cmp_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } int missingNumber(int* nums, int numsSize) { qsort(nums, numsSize, sizeof(int), cmp_int); int i = 0; for (i = 1; i < numsSize; i++) { if (nums[i] - nums[i - 1] != 1) { return nums[i] - 1; } } if(nums[0] == 0) { return nums[numsSize-1] + 1; } return 0; }

方法2.

        利用等差数列的公式 n * (n-1) / 2 算出总数和再减去数组中的数就能找到

int missingNumber(int* nums, int numsSize) { int x = (1 + numsSize) * numsSize / 2; int i = 0; for(i = 0; i < numsSize; i++) { x -= nums[i]; } return x; }

方法3.

        使用０跟 0到ｎ之间的数异或，再跟数值中的值异或，就能得到答案（找出单身狗问题）

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

 2.撞色搭配

        撞色搭配

        题述：整数数组 sockets 记录了一个袜子礼盒的颜色分布情况，其中 sockets[i] 表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子，每种颜色的袜子均有两只。请设计一个程序，在时间复杂度 O(n)，空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。

示例 1：

输入：sockets = [4, 5, 2, 4, 6, 6] 输出：[2,5] 或 [5,2] 

示例 2：

输入：sockets = [1, 2, 4, 1, 4, 3, 12, 3] 输出：[2,12] 或 [12,2]

题解：

通过0对自身依次异或，将两个单独的数的异或后的结果找出，再通过结果将两个值分离开来，找到异或后结果的二进制序列，找出为1的位数（如果为1，则说明两个单独数在这个位不相同，可凭此将两个数分离），找到位数后，将按其他数的这个位数是否为1，还是为0分离，这就形成了两组数，在分别自身异或，最后剩下的就是单独数。

int* sockCollocation(int* sockets, int socketsSize, int* returnSize) { int ret = 0; int i = 0; for(i = 0; i < socketsSize; i++) { ret ^= sockets[i]; } int pos = 0; for(i = 0; i < 32; i++) { if(((ret >> i) & 1) == 1) { pos = i; break; } } int dog1 = 0; for(i = 0; i < socketsSize; i++) { if(((sockets[i] >> pos) & 1) == 1) { dog1 ^= sockets[i]; } } int dog2 = dog1 ^ ret; int* arr = (int*)malloc(8); arr[0] = dog1; arr[1] = dog2; *returnSize = 2; return arr; }

3.轮转数组

   轮转数组

  给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 

输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]

方法1.

暴力求解：从最后一项开始向前交换，交换到头相当于完成一次轮转。

                                  （此方法最差时间复杂度为O(N²)，会超时）

void rotate(int* nums, int numsSize, int k) { k %= numsSize; int i = 0; for(i = 0; i < k; i++) { int j = 0; for(j = numsSize-1; j > 0; j--) { int tmp = nums[j]; nums[j] = nums[j-1]; nums[j-1] = tmp; } } }

方法2.

三步翻转法，时间复杂度为O(N)

void rotate(int* nums, int numsSize, int k) { k %= numsSize; int i = 0; int tmp = 0; int j = 0; for(i = 0,j = numsSize-k-1; i < j; i++,j--) { tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } for(i = numsSize-k,j = numsSize-1;i<j;i++,j--) { tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } for(i = 0,j = numsSize-1; i < j; i++,j--) { tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }

方法3.

开辟一个数组，用空间换时间，时间复杂度O(N)

void rotate(int* nums, int numsSize, int k) { int* arr = (int*)malloc(sizeof(int) * numsSize); int i = 0; int j = 0; k %= numsSize; for(i = numsSize - k, j = 0; i < numsSize; i++, j++) { arr[j] = nums[i]; } for(i = 0; i < numsSize - k; i++, j++) { arr[j] = nums[i]; } for(i = 0; i < numsSize; i++) { nums[i] = arr[i]; } }