数据结构与算法（复杂度）

风中的云彩

发布于 2024-11-07 21:51:16

900

文章被收录于专栏：C/C++的自学之路

很多时候，咨询的人心里已经有了答案，来咨询只是想确认自己的决定是对的。

前言

这是我学习数据结构的第一份笔记，有关复杂度的知识。后期我会继续将数据结构知识的笔记补全。

数据结构含义

1. 通过数据结构，有利于把杂乱无章的数据，进行管理操作。 2. 数据结构主要用于程序设计，而非数值计算。 3. 数据结构分为逻辑结构和物理结构。

逻辑结构

1. 集合结构。 2. 线性结构。 3. 树形结构。 4. 图形结构。

物理结构

1. 顺序储存结构：逻辑结构是线性的，物理结构也是线性的、连续的。（数组） 2. 链表储存结构：逻辑结构是线性的，物理结构却是非线性的、非连续的。（链表）

算法的含义

1. 通过一系列的计算步骤，将输入的数据转化成结果。 2. 算法的特性：输入输出、有穷性、确定性、可行性。

复杂度

复杂度的含义

1. 复杂度用来衡量一个算法的好坏。 2. 复杂度分为时间复杂度和空间复杂度。 3. 时间复杂度（主要）：算法运行的快慢。 4. 空间复杂度：算法运行所需要的额外空间。

时间复杂度

1. 可以表示为一个函数式：T(N) 。 2. T(N)等于一个具体的复杂度。

计算时间复杂度的公式

1. n：程序运行时间效率。 2. a：每条语句的运行时间（注：a不是一个确定的值，与编译环境有关。） 3. b：每条语句的运行次数（注：b是一个确定的值。）

计算程序运行时间

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <time.h>
int main()
{
	int begin=clock();//记录程序刚开始的时间
	int count = 0;
	for (int i = 0; i < 10000000; i++)
	{
		count++;
	}
	int end = clock();//记录程序刚结束的时间
	printf("%d", end - begin);//需要在debug模式下
	return 0;
}
//多运行几次都不同，没有精确值

大O的渐进表示法

1. 大O符号：用于描述函数渐进行为的符号。例如：O（N^2） 2. 我们通过大O的渐进表示法，来计算运行的次数。 3. O（）括号里面写的是一个具体复杂度的约数。 4. 大O的渐进表示法的规则：

如果存在最高阶项，则忽略最高阶项系数和其他低阶数项，只看最高阶项。
如果只有常数项，则直接视为1。
重点看循环或递归次数。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <time.h>
void Func1(int N) 
{
    int count = 0;
    // 第一个循环：N * N 次迭代
    for (int i = 0; i < N; ++i) 
    {
        for (int j = 0; j < N; ++j) 
        {
            ++count;
        }
    }
    // 第二个循环：2 * N 次迭代
    for (int k = 0; k < 2 * N; ++k) 
    {
        ++count;
    }
    // while 循环：10 次迭代
    int M = 10;
    while (M--) 
    {
        ++count;
    }
}
    //T(N)=N^2+2N+10
    //复杂度为:O(N^2)

void Func2(int N)
{
    int count = 0;
    // 这个循环将执行 2 * N 次
    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    }
    // 这个循环将执行 10 次
    int M = 10;
    while (M--)
    {
        ++count;
    }
    printf("%d\n", count);
}
    //T(N)=2*N+10
    //复杂度为：O(N)

void Func3(int N, int M)
 {
    int count = 0;
    // 这个循环将执行 M 次
    for (int k = 0; k < M; ++k)
    {
            ++count;
    }
    // 这个循环将执行 N 次
    for (int k = 0; k < N; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}
    //T(N)=M+N
    //复杂度为：O(M+N)

void Func4(int N) 
{
    int count = 0;
    // 这个循环将执行 100 次
    for (int k = 0; k < 100; ++k) 
    {
        ++count;
    }
    printf("%d\n", count);
}
    //T(N)=100
    //复杂度为:O(1)

const char * strchr ( const char* str, int character)
{
    const char* p_begin = s;
    while (*p_begin != character)
    {
        if (*p_begin == '\0')
        {
                return NULL;
         }
        p_begin++;
    }
    return p_begin;
}

    //上界：最坏的情况O(N)，若要查找的字符在字符串第⼀个位置。
    //下界：最好的情况O(1)，若要查找的字符在字符串最后的⼀个位置。
    //主要关注上界最差的情况

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define N
int main()
{
	int arr[N] = { 0 };
	int i = 0;
	for (i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]);
	}
	int a = 0, b = 0;
	for (a = 0; a < N-1; a++)
	{
		for (b = 0 ; b < N-1-a; b++)
		{
			if (arr[b] > arr[b + 1])
			{
				int mid = 0;
				mid = arr[b + 1];
				arr[b + 1] = arr[b];
				arr[b] = mid;
			}
		}
	}
	for (i = 0; i < N; i++)
	{
		printf("%d\n", arr[i]);
	}
	return 0;
}
    //T(N)=N(N-1)/2
    //复杂度为:O(N^2)

void func5(int n) 
{
    int cnt = 1;
    while (cnt < N) 
    {
        cnt *= 2;
    }
}
    //T(N)=log（N）,不管底数。

long long Fac(size_t N) 
{
    if (0 == N)
    {
        return 1;
    }
    return Fac(N - 1) * N;
}
    //T(N)=N
    //复杂度为:O(N)

上下界

1. 最坏情况：任意输入规模的最大运行次数(上界)。 2. 平均情况：任意输入规模的期望运行次数。 3. 最好情况：任意输入规模的最小运行次数(下界)。 4. 但在实际情况中，只考虑最坏情况。

空间复杂度

计算空间复杂度

1. 专指函数在运行时所额外占用的空间。 2. 规则与时间复杂度相同。 3. 重点看定义的变量个数。

void BubbleSort(int* a, int n) 
{
    assert(a);
    for (size_t end = n; end > 0; --end) //第一个end
    {
        int exchange = 0;//第二个exchange
        for (size_t i = 1; i < end; ++i) //第三个i
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}
    //空间复杂度为:O(1)

long long Fac(size_t N) 
{
    if (N == 0)
        return 1;
    return Fac(N - 1) * N;
}
    //空间复杂度为:O(N)，每一次递归，空间复杂度增加一次。

复杂度的大小比较

总结

若在算法题型中，如果时间复杂度超过要求，则可以提高空间复杂度来降低时间复杂度。

例题：轮转数组

将一个数组的元素向后移 k 位。

void rotate(int* nums, int numsSize, int k)
{
    while(k--)
    {
        int end = nums[numsSize-1];
        for(int i = numsSize - 1;i > 0 ;i--)
        {    
            nums[i] = nums[i-1];
        }
        nums[0] = end;
    }
}
//通过两个内外层循环从而达到目标

改进后：
void rotate(int* nums, int numsSize, int k)
{
    int newArr[numsSize];
    for (int i = 0; i < numsSize; ++i)
    {
        newArr[(i + k) % numsSize] = nums[i];
    }
    for (int i = 0; i < numsSize; ++i)
    {
        nums[i] = newArr[i];
    }
}
//通过创建一个新的数组从而达到目标