1.复杂度[数据结构与算法]

什么是数据结构

数据结构是计算机存储,组织数据的方式,相互之间存在一种或多种特定关系

什么是算法

Algorithm:定义良好的计算过程,取一个输入,产生一个输出
算法就是一系列的计算步骤,将输入数据转化成输出结果

排序就是一种常见的算法
如:二分查找

重要性

校招笔试 OJ形式
20-30选择题,3-4编程题
校招面试,数据结构与算法权重很高

复杂度

算法效率

时间效率,空间效率

时间复杂度

概念

算法中基本操作的执行次数就是算法的时间按复杂度
算法的时间复杂度是一个函数

实际情况中,不能真正计算时间,(不同机器/环境不一样)

八核即八个CPU 64G内存
双核4G

大O的渐进表示法

时间复杂度计算,大O的渐进表示法---估算
2n^2+2n+10--->O(n^2)
n->∞时,f(n)->n^2
算法的时间复杂度是一个函数,取函数表达式中,最影响结果的一项
Big O notation 大O符号
取最高阶那一项,并去掉系数
如果是常数,则是O(1)
    
Fun(100) 不能认为它是O(1)
看的是算法,而不是某一次具体的调用
函数传进去的值可以是任意的
    
    比如:
strchar("abcdef",'x');//这次调用中,字符串长度为6,难道复杂度就是O(1)吗
1
2
3
4
5
6
7
8
9
10
11
12
13
14

O(M+N) M,N是常数
而不是O(1)
M N不知道谁大谁小

O(1)表示它是常数次,10w,100w也是O(1)

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
int main()
{
       int n = 100000000;
       int begin = clock();
       for (int i = 0; i < n; ++i)
       {
           
       }
       int end = clock();
       printf("%d\n", end - begin);
       //clock 显示的程序执行开始的时间戳,单位是毫秒
       //1亿次只花了39ms
       return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

一万次还是一亿次都是瞬间运行完毕 几十ms级别
硬件的飞速发展,CPU运行速度太快了

时间复杂度计算中,通常假设数组/字符串长度是N
在一个长度为N数组中找一个数据,最好一次找到,最坏N次
平均N/2,但面对这种情况,默认时间复杂度看最坏的
O(N)

冒泡排序:
N-1+…+1=N(N-1)/2—>O(N^2)

void bubble_sort(int arr[], int sz)
{
	int i = 0;
	int j = 0;
	//趟数
	for ( i = 0; i < sz-1; i++)
	{
		//每一趟冒泡排序的过程  
		//10元素 9躺 比较8对
		//需要比较的对数每一趟-1
		for (j = 0; j < sz-1-i; j++)
		{
			if (arr[j+1] < arr[j])//升序
                //如果是字符串排序，不能用><号
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

练习

面试题 17.04. 消失的数字

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

思路1:冒泡排序–>O(N^2) 排好序后再比较就行 看前一个数+1是否等于后一个数

或者qsort(快速排序) 底层是快排 O(N* logN)也不满足O(N)

思路2:0~n 计算等差数列的和 - 数组中值相加
O(1) O(N)

思路2

int missingNumber(int* nums, int numsSize)
{
   int n = numsSize+1;
   int ret1 =0;
   // 0-n之间所有值累加 O(1)
   for(int i = 0; i < n; i++)
   {
       ret1 += i;
   }
   int ret2 = 0;
   // 数组中所有值累加
   for(int j = 0; j < numsSize ; j++)
   {
       ret2 += nums[j];
   }
   return ret1 - ret2;
}
//时间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路3

 思路3: 异或
 0~n数字和数组中的值依次异或,结果就是缺失的数字
     
 两个相同的数异或==0
 9 6 4 2 3 5 7 0 1
 0 1 2 3 4 5 6 7 8 9
 依次异或只剩下8了
 不需要排序
 [3 0 1]
 0 1 2 3
 3---0011
 0---0000
 3^0->0011 3
 3^0^1-->0011^0001-->0010-->2
 0010^0000-->0010
 0010^0001-->0011
 0011^0010-->0001
 0001^0011-->0010--->2
 3^0^1^0^1^2^3--->2

 1^3^1--->3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

异或不需要考虑顺序,只要最终2个相同的数异或了,就会没了

int missingNumber(int* nums, int numsSize)
{
    int x = 0;
    for(int i = 0; i < numsSize + 1; ++i)
    {
        x ^= i;
    }
    for(int j = 0; j < numsSize; ++j)
    {
        x ^= nums[j];
    }
    return x;
}
//这样写更清晰
1
2
3
4
5
6
7
8
9
10
11
12
13
14

int missingNumber(int* nums, int numsSize)
{
    int x = 0;
    for(int i = 0; i < numsSize + 1; ++i)
    {
        x ^= i;
        if(i < numsSize)
        {
            x ^= nums[i];
        }
    }
    
    return x;
}
//一个循环的形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

136. 只出现一次的数字

不使用额外的空间,表示的是常数个空间
线性时间复杂度即O(N)

int singleNumber(int* nums, int numsSize)
{
    int x = 0;
    for(int i = 0; i<numsSize; i++)
    {
        x ^= nums[i];
    }
    return x;
}
1
2
3
4
5
6
7
8
9

剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

ret = 0,将数组中所有数都跟ret异或一下
这样就消除掉出现2次的数了
ret=x^y
2.
ret必定不为0,找ret里面随便一个为1的位,说明x y对应位一个为1有一个为0
把原数组中的数,第n位为1的分成1组,第n位为0的分成一组
1 3 1 2 5 2
比如 第一位为1分成一组,第一位为0分成一组
3 2 2 1 1 5
再对他们分别异或

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 //returnSize 表示找出来的2个数得返回,以数组的形式返回
int* singleNumbers(int* nums, int numsSize, int* returnSize)
{
    int ret = 0;
    for(int i = 0; i < numsSize; i++)
    {
        ret ^= nums[i];
    }
    
    //找ret里一个为1的位
    int j = 0;
    for(; j < 32; ++j) 
    {
        if(ret & (1<<j)) // if(ret>>j & 1)y
        {
          break;
        }
        // ret的第j位为1,说明x y两个的第j位一个为1,一个为0
    }
    
    // 将原数组分为2组,第j位为1的一组,第j位为0的一组
    //x y一定会分别进入a b组,其他出现2次的数要么进a组,要么进b组
    //a组和b组数据就会变成其他数出现2次,只有一个数出现1次,再分别异或就行
    int x = 0;
    int y = 0;
    for(int k = 0; k < numsSize; ++k)
    {
        if(nums[k] & (1<<j))    //a组
        {
            x ^= nums[k];
        }
        else                    //b组
        {
            y ^= nums[k];
        }
    }
    int* arr = (int*)malloc(sizeof(int)*2);
    arr[0] = x;
    arr[1] = y;
    *returnSize = 2;//输出型参数,让外面拿到数组长度
    return arr;
}

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

注意:比较严格的编译器,不允许int的1左移31位,因为会跑到符号位上
可以考虑用右移
或者强制转换成另一个类型 long long 或者unsigned int

剑指 Offer II 004. 只出现一次的数字

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

int singleNumber(int* nums, int numsSize)
{
   unsigned int arr[32] = {0};
   //int是有符号的   最高位是符号为   有效数据为只有31位
   //改成无符号后 所有的bit位都是数据位
    int count = 0;
    int k = 31;
    for(int i = 0;i < 32;i++)
    {
        for(int j = 0;j < numsSize;j++)
        {
            count += ((nums[j]>>i) & 1);
        }
        arr[k] = count;
        count = 0;
        k--;
    }
    for(int i = 0;i < 32;i++)
    {
        arr[i] %= 3;
    }
    int ret = 0;
    for(int i = 0;i < 32;i++)
    {
        ret |=(arr[31-i]<<i); //此处Leetcode上编译不通过
    }
    return ret;
}

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

思路：
由于这次其他数字出现的次数是奇数次，全部一起异或无法消除掉其余的数字。因此我们要换种方法。
把数组中所有的数的每一个二进制位加起来放进一个数组，然后%3，最后得到的数字就是那个只出现一次的数字。
由于其他数字都出现了三次，因此它们的那一位二进制位一定是3的倍数。%3相当于把那些重复的位全部减去了，剩下的二进制位就是只出现一次的数字的二进制位。

步骤：
先用按位与把每一位二进制位拿出来并相加存进数组中
再把数组中的数字都%3
用按位或把数组中的数字操作在ret上

   //int是有符号的   最高位是符号为   有效数据为只有31位
   //改成无符号后 所有的bit位都是数据位
1
2

//写到一起简洁
int singleNumber(int *nums, int numsSize) {
    int ans = 0;
    for (int i = 0; i < 32; ++i) {
        int total = 0;
        for (int j = 0; j < numsSize; ++j) {
            total += ((nums[j] >> i) & 1);
        }
        if (total % 3) {
            ans |= (1u << i);
        }
    }
    return ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二分查找

最好:O(1)
二分查找也叫折半查找
时间复杂度里面,习惯简写成logN
有些资料会写成lgN 严格来说这是不对的,跟数学中混乱了
二分查找需要数据先排好序
可以用qsort快速排序
先排序–>二分查找
qsort时间复杂度N* logN
二分查找logN
排完序后二分查找就快了,多次查找方便

红黑树/哈希表才是真正用来查找的算法

递归算法

递归算法时间复杂度=递归次数* 每次递归函数中次数
Fac(N)–>Fac(N-1)–>…Fac(1)
也就是N*1(1代表的是常数次)
时间复杂度O(N)

如果再套一层for循环,则就是O(N^2)

斐波那契数列

注意需要减去提前完成的Fib,可以忽略掉
可以估算CPU的运行效率,一般都是亿级别
2^30 约等于 10亿

#include<time.h>
long long Fibonacci(size_t N)
{
       return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2);
}
int main()
{
       int begin = clock();
       Fibonacci(40);
       int end = clock();
       printf("%d\n", end - begin);
}
/*
40算了3339ms,45算了36351ms
这个算法时间复杂度太高,在实际中没有意义
O(2^N)
考虑改成循环--->O(N)
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include<stdio.h>
//复杂度O(N)
int fib(int n)
{
       int a = 1;
       int b = 1;
       int c = 1;//n = 1/2 不走循环直接返回1
       while (n > 2)
       {
               c = a + b;
               a = b;
               b = c;
               n--;
       }
       return c;
}
int main()
{
       int n = 0;
       scanf("%d", &n);
       int ret = fib(n);
       printf("%d\n", ret);
       return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

空间复杂度

随着技术的发展,对空间的要求比较低了,不太关注空间复杂度了
空间复杂度不是去算程序占用多少bytes
算的是变量的个数

冒泡排序

冒泡排序空间复杂度O(1) — 常数个空间
不考虑输入的数字,考虑的是算法运行中额外搞的空间
时间是累计的,空间不累计,空间是可以复用的
第一次用的是那个空间,结束了销毁了下次用的还是那片空间

斐波那契

开了n+1个空间就是O(N)
不是针对某一次调用考虑复杂度,而是针对算法

递归

每次调用会创建函数栈帧
每个栈帧里面是常数个空间