数据结构_Java

数据结构_时空复杂度

前言：此类笔记仅用于个人复习，内容主要在于记录和体现个人理解

文章目录

- - 数据结构_时空复杂度
- @[toc]
- - - 算法效率
    - 时间复杂度
    - - 时间复杂度本质上是一种函数
      - 表示方法：大O的渐进表示法
      - 推导O的方法
      - 递归算法时间复杂度
    - 空间复杂度
    - 常见复杂度
    - 一些题目

算法效率

算法效率是用来衡量一种算法的好坏的指标

简洁的代码不一定好，比如典型的斐波那契数列

衡量算法的好坏要看时间复杂度和空间复杂度

时间复杂度衡量的算法的运行快慢

空间复杂度衡量的是算法运行时需要额外开辟的空间

时间复杂度时间复杂度本质上是一种函数表示方法：大O的渐进表示法

时间复杂度是算法中基本操作的执行次数，不是秒数

是一种“悲观”的表示法

一般计算的都是最大的执行次数

计算的是量级，不是具体的确切数字

推导O的方法

用常数 1 代替运算时间中的所有加法常熟（因为量级是常数级）

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

因为对于量级来说，只有最高阶有决定性作用

如果最高阶存在不是 1，则把最高阶的常数系数换为 1

递归算法时间复杂度

每次函数调用是O(1)，那么就看它的递归次数（函数调用次数就是函数体中的运算次数，如果没有循环一般就是O(1) ）

每次函数调用不是O(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("%dn", count);
}
基本操作执行了2N+10次，大O渐进表示法就是O(N)
// 计算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("%dn", count);
}
基本操作执行了M+N次，而带入到算法中的未知数也有两个，分别是M和N，因此是O(M+N)
// 计算Func4的时间复杂度? 
void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++ k)
    {
      ++count;
    }
    printf("%dn", count);
}
O(1)
const char * strchr ( const char * str, int character );
这是字符查找函数，返回在参数（字符串）中第一次出现要查找的字符的位置

通过遍历的方式查找，最好是第一次就能找到，最坏是第N次，因此是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;
      }
}
冒泡排序，最好的情况是本来就是有顺序的，只需要遍历一次就可以了，执行N-1次

最坏的情况是顺序是完全相反的

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值 ———百度百科

执行次数是(N*(N+1)/2次，按照大O表示法就是O(N^2)

因此时间复杂度就是O(N^2)
// 计算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
    }
}
二分查找，又称折半查找，前提是数组必须是有序的c

通过与每次与有序数组的中间元素进行大小比较，将范围缩小为原来的一半

最好的情况是第一次就找到（要查找的正好是中间元素），最坏的情况是找不到（那就要找到底），是logN次（底数为2）

O(logN)
// 计算阶乘递归Fac的时间复杂度? 
long long Fac(size_t N)
{
    if(0 == N)
        return 1;
    return Fac(N-1)*N;
}
调用次数是O(1)

递归次数是N

O(N)
// 计算斐波那契递归Fib的时间复杂度? 
long long Fib(size_t N)
{
    if(N < 3)
        return 1;
    return Fib(N-1) + Fib(N-2);
}
这个斐波那契函数函数调用次数是O(1)

递归次数是2^N

O(2^N)

空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用空间大小的量度

空间复杂度计算的不是在算法运行过程中占用的系统的bytes(字节)数，因为这样也没什么意义

计算的是变量个数

计算规则也是大O的渐进表示法

注意: 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

几个例子
// 计算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;
    }
}
变量是具有作用域的，出了作用域就会释放，将权限归还给操作系统，不算占用

每次进入for循环的时候只生成一个额外的变量

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;
}
动态开辟数组为N个，O(N)
// 计算阶乘递归Fac的空间复杂度? 
long long Fac(size_t N)
{
    if(N == 0)
        return 1;
    return Fac(N-1)*N;
}
递归调用了N次，一共开辟个N个栈帧，每个栈帧使用了常数个空间，空间复杂度是O(N)

常见复杂度

一些题目

1.消失的数字 https://leetcode-cn.com/problems/missing-number-lcci/

方法一：排序

冒泡O(N^2)

qsort(N*logN)

方法二：映射

根据元素个数重新开辟一个元素个数为size的数组new，元素初始化为-1。遍历原数组中的每个数n，并按顺序映射到new中，new[n]=n。最后new中仍为-1的权重就是消失的数字。

方法三：异或

按位异或

两个十进制数字转化为二进制之后的每个二进制位进行比较，每个二进制位相同为0，相异为1，多个数字比较时不用考虑顺序（不影响结果）

解题思路：

定义一个val赋值为0，先依次跟0-n异或，并把结果赋值给自己（val^=)

然后再跟数组里的每个元素异或，最后得到的结果就是消失的数字

因为异或顺序不影响结果，相当于

这样0-n跟数组中如果有重复的数字，异或之后结果为零，数组中消失的数字在0-n中落单，跟val（值为零）异或之后值还是它本身。

基本操作的执行数是(N-1)+N

O(N)

方法四：

利用等差数列计算

0-n本身就是一种等差数列，根据求和公式减去数组各元素，剩下的值就是消失的数字

O(N)

2.旋转数组https://leetcode-cn.com/problems/rotate-array

输入：nums = [1,2,3,4,5,6,7] , k=3

输出：[5,6,7,1,2,3,4]

方法一：

重新开辟一个长度为n的数组news，nums的后k项赋值给new的前k项，前n-k项复制给new的后n-k项

时间复杂度O(N)

空间复杂度O(N)

方法二：

右旋k次，一次移动一位（最后一个元素赋值给tmp，前面的元素依次向前赋值）

每次时间复杂度是N，一共执行k%N次，总计N*(k%N)次

如果k%N=1，那么时间复杂度是O(N)

如果k%N=N-1，那么时间复杂度是O(N^2)，这种情况是最差的

所以时间复杂度是O(N^2)

空间复杂度是O(1)

方法三：用规律

时间复杂度O(N)

空间复杂度O(1)

数据结构

Java相关栏目本月热门文章