C语言数据结构--详细讲解算法复杂度

标签：arr -- 复杂度 C语言 int 算法 时间 执行

C语言数据结构-算法复杂度

• 前言
• 一、时间复杂度
• • 1.大O渐进表示法
  • 2 时间复杂度的计算
• 二、空间复杂度
• • 1.什么是空间复杂度
  • 2 时间复杂度的计算
• 总结

---

前言

我们都清楚计算机存储和组织数据是通过数据结构来实现的。当计算机对这些数据结构中的数据进行遍历等操作时，这个过程就是我们所说的算法。算法的性能对于计算机处理数据的效率至关重要，这里就需要引入算法复杂度这一概念了。算法复杂度主要涵盖了时间复杂度和空间复杂度，时间复杂度用于衡量算法执行时间随数据规模变化的情况，空间复杂度则用于评估算法运行时占用额外空间与数据规模的关系，它们是评估算法优劣的关键指标。

---

一、时间复杂度

• 在计算机科学中，算法的时间复杂度是函数式T(N)，它主要衡量程序的时间效率。那为什么不直接计算程序运行时间呢？
  这是因为程序运行时间受编译环境和机器配置影响。比如，同一个算法程序，用老编译器和新编译器编译后，在相同机器上运行时间不同；在老低配置机器和新高配置机器上运行，时间也不同。

• 影响时间复杂度的主要条件包括每条语句的执行时间和执行次数。然而，通常情况下，尽管每条语句的执行时间可能存在差别，但这种差别往往微乎其微，可以忽略不计。因此，可以认为每条语句的执行时间是相同的，所以影响时间复杂度的重要条件只有每条语句的执行次数。

1.大O渐进表示法

• 时间复杂度衡量的是算法执行时间与输入规模的增长趋势关系，不是具体执行时间，毕竟执行时间会受硬件、编程语言实现细节等多种因素干扰。因此我们常用大O渐进表示法（如O(1)、O(n)、O(n²)等）表示时间复杂度。

下面给大家详细讲解一下大O渐进表示法的规则

（1）.时间复杂度函数式 T (N) 只保留最高阶项，低阶项在 N 无穷大时可忽略不计。

例如 T (N)=N² + 3N + 5，当 N 趋于无穷大时，低阶项 3N 和常数项 5 对结果的影响越来越小，可以忽略不计，最终时间复杂度为 O (N²)

（2）.若最高阶项存在且不是 1，去除该项的常数系数，因 N 变大时其影响越来越小。

例如 T (N)=2N² + 4N + 6，去除最高阶项的系数 2，时间复杂度为 O (N²)。

（3）.T (N) 中若无 N 相关项只有常数项，用常数 1 取代所有加法常数。

例如 例如 T (N)=7，可简化为时间复杂度为 O (1)。

2 时间复杂度的计算

void Timecomplexity(int n) 
{
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", i);
    }
}
 

根据时间复杂度的重要条件 ：

影响复杂度的重要条件只有每条语句的执行次数

这里有一个 for 循环从 1 到 n ，循环内执行一次加法操作（时间复杂度为 O(1) ），总共执行 n 次，所以时间复杂度是 O(n) 。

// 冒泡排序函数
void bubble_sort(int arr[], int n) 
{
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n - i - 1; j++) 
        {
            if (arr[j] > arr[j + 1])
             {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

• 第一次内层循环for (int j = 0; j < n - i - 1; j++)执行n - 1次。
  第二次内层循环执行n - 2次。
  内层循环的总执行次数是(n-1)+(n -2)+(n -3)+…+1，这是一个等差数列求和，结果为**(n(n-1)/2)**
  从上面的分析可以看出，内外层循环的总执行次数与n²同阶，忽略低阶项和系数后，该函数的时间复杂。
  度为O(n²)。

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);
}

• for循环执行2 * N次
  while循环执行 10 次
  总的执行次数是2 * N+ 10
  根据时间复杂度的定义，忽略常数项和低阶项，时间复杂度为O(n)

void func5(int n)
{
    int cnt = 1;
    while (cnt < n)
    {
        cnt *= 2;
    }
}

• 在每次循环中，cnt的值会翻倍,假设循环执行了k次，那么cnt的值会变成2^k。
• 当2^k >= n时，循环结束。
• 解这个不等式2^k >= n，得到k >= log₂n
  因此，这个循环的时间复杂度是O(logn).

二、空间复杂度

1.什么是空间复杂度

• 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
• 空间复杂度的计算方法与时间复杂度类似，一般用算法所占用的额外空间的大小来衡量，通常以特定的数据规模下所需的存储空间大小来表示。

例如，如果一个算法需要开辟一个大小固定为 n 的数组，那么它的空间复杂度就是 O (n)；如果算法只需要几个固定的变量，不随输入规模的变化而变化，那么它的空间复杂度就是 O (1)。
空间复杂度分析有助于了解算法在存储资源方面的需求，对于处理大规模数据或者在资源受限的环境中非常重要。

2 时间复杂度的计算

我们直接用时间复杂度的最后一道题来对比一下

void func5(int n)
{
    int cnt = 1;
    while (cnt < n)
    {
        cnt *= 2;
    }
}

• 在这个函数中，只定义了一个整数变量 cnt，无论输入 n 的值是多少，始终只使用了一个固定大小的额外存储空间，不随输入规模 n 的变化而变化。
  所以这个函数的空间复杂度为 O (1)。

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);
}

• 定义了一个整数变量 count，无论输入 N 的值是多少，这个变量占用的空间都是固定的。
  定义了一个整数变量 M，同样占用固定大小的空间。
  所以该函数的空间复杂度为 O (1)。

void createArray(int n) 
{
    int* arr = (int*)malloc(n * sizeof(int));
    // 动态分配 n 个整数大小的内存空间，并将其地址赋值给指针 arr
    free(arr);
}

• 在这个函数中，通过 malloc 动态分配了 n * sizeof(int) 的内存空间，分配的内存空间大小与 n 成正比，空间复杂度为O（n）；

总结

• 简单介绍了 C 语言中时间复杂度和空间复杂度。
• 时间复杂度用于衡量算法执行时间随输入规模变化的情况，通过大 O 渐进表示法来表示，主要考虑算法中每条语句的执行次数。
• 空间复杂度则是对算法在运行过程中临时占用存储空间大小的量度，通常以特定数据规模下所需的存储空间大小来表示，计算方法与时间复杂度类似。
• 了解算法的复杂度有助于我们评估算法的优劣，在处理大规模数据或资源受限的环境中选择合适的算法。

最后的最后给大家推测一道算法复杂度的例题

/旋转数组

标签：arr,--,复杂度,C语言,int,算法,时间,执行
From： https://blog.csdn.net/2402_83322742/article/details/143573060