重生之我在异世界学编程之算法与数据结构：算法复杂度介绍篇

news/2024/12/19 6:28:44/

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

本文目录

  • 引言
  • 正文
    • 一 时间复杂度
      • 1. 常数时间复杂度 O(1)
      • 2. 线性时间复杂度 O(n)
      • 3. 对数时间复杂度 O(log n)
      • 4. 平方时间复杂度 O(n^2)
      • 5. 指数时间复杂度 O(2^n)
    • 二 空间复杂度
      • （1）空间复杂度的定义与重要性
      • （2）常见的空间复杂度类型及介绍
        • 1.常数空间复杂度 O(1)
        • 2.线性空间复杂度 O(n)
        • 3.多项式空间复杂度 O(n^k)（k为常数）
        • 4. 动态分配的内存（可变空间复杂度）
      • （3）空间复杂度的分析方法
    • 三 空间复杂度与时间复杂度的关系
    • 四 常见算法的复杂度分析
      • 1. 线性搜索
      • 2. 二分搜索
      • 3. 冒泡排序
  • 快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！

引言

在计算机科学中，算法是解决问题的核心工具。当我们设计或选择一个算法时，通常需要考虑两个关键因素：时间复杂度和空间复杂度。这两个指标帮助我们衡量算法的效率和资源消耗情况。本文将深入探讨C语言中常见的数据结构及其相关算法的复杂度分析，并通过代码示例进行具体说明。那现在，一起来看看吧！！！

在这里插入图片描述

那接下来就让我们开始遨游在知识的海洋！

正文

一 时间复杂度

  • 定义：时间复杂度是衡量算法执行时间长短的一个标准，它反映了算法随着输入规模增大而增长的趋势。通常用“大O符号”（O-notation）来表示。

1. 常数时间复杂度 O(1)

  • 常数时间复杂度意味着无论输入规模如何变化，算法的执行时间都保持不变。例如，访问数组中的某个元素就是O(1)操作。

例：

 
#include <stdio.h>int getElement(int arr[], int index, int size) {if (index >= 0 && index < size) {return arr[index]; // 直接访问数组元素，时间复杂度为O(1)} else {return -1; // 错误处理}
}int main() {int arr[] = {1, 2, 3, 4, 5};printf("%d
", getElement(arr, 2, 5)); // 输出3return 0;
}

2. 线性时间复杂度 O(n)

  • 线性时间复杂度表示算法的执行时间与输入规模成正比。例如，遍历一个数组的所有元素就是O(n)操作。

例·：

 
#include <stdio.h>void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]); // 遍历数组，时间复杂度为O(n)}printf("
");
}int main() {int arr[] = {1, 2, 3, 4, 5};printArray(arr, 5); // 输出整个数组return 0;
}

3. 对数时间复杂度 O(log n)

  • 对数时间复杂度常见于二分查找等基于分治策略的算法中。其特点是指数级减少的搜索范围。

例·：

 
#include <stdio.h>int binarySearch(int arr[], int target, int left, int right) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标，返回索引} else if (arr[mid] < target) {left = mid + 1; // 在右半部分继续搜索} else {right = mid - 1; // 在左半部分继续搜索}}return -1; // 未找到目标
}int main() {int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};int target = 7;int result = binarySearch(arr, target, 0, 9);if (result != -1) {printf("Found %d at index %d
", target, result);} else {printf("%d not found in array
", target);}return 0;
}

4. 平方时间复杂度 O(n^2)

  • 平方时间复杂度通常出现在嵌套循环结构中，如冒泡排序和选择排序。

冒泡排序示例：

#include <stdio.h>void bubbleSort(int arr[], int size) {for (int i = 0; i < size - 1; i++) {for (int j = 0; j < size - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("
");
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int size = sizeof(arr)/sizeof(arr[0]);bubbleSort(arr, size);printf("Sorted array: 
");printArray(arr, size);return 0;
}

5. 指数时间复杂度 O(2^n)

  • 指数时间复杂度通常出现在递归调用未进行优化且问题规模迅速增大的情况下，如斐波那契数列的直接递归实现。
 
// 未经优化的斐波那契数列计算
#include <stdio.h>int fibonacci(int n) {if (n <= 1) {return n;} else {return fibonacci(n - 1) + fibonacci(n - 2);}
}int main() {int n = 10;printf("Fibonacci number is %d
", fibonacci(n));return 0;
}

二 空间复杂度

（1）空间复杂度的定义与重要性

  • 空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间大小的量度。它反映了算法在执行过程中对内存使用的需求，是评价算法效率的重要指标之一。与时间复杂度类似，空间复杂度也使用大O记号来渐进地表示。

（2）常见的空间复杂度类型及介绍

1.常数空间复杂度 O(1)
  • 算法所需的额外空间是一个常数，与输入规模无关。这意味着不随着输入数据的增加而增加额外的存储空间。例如，在交换变量的操作中，只使用了一个额外的变量temp，无论输入的数据是什么规模，都只需要常数级别的额外空间。

例如，一个简单的交换两个整数值的函数：

#include <stdio.h>void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}int main() {int x = 5, y = 10;swap(&x, &y);printf("x = %d, y = %d
", x, y); // 输出: x = 10, y = 5return 0;
}

在这个例子中，swap 函数只使用了一个额外的变量 temp 来存储临时值，因此它的空间复杂度是 O(1)。

2.线性空间复杂度 O(n)
  • 算法所需的额外空间与输入规模成线性关系。例如，需要一个与输入规模相等的数组来存储数据，或者递归函数中每次调用都会占用一定的栈空间，调用次数与输入参数n成线性关系。常见的具有线性空间复杂度的算法包括复制数组、字符串拼接等。

例如，一个计算数组中所有元素之和的函数：

#include <stdio.h>int sumArray(int arr[], int size) {int sum = 0;for (int i = 0; i < size; i++) {sum += arr[i];}return sum;
}int main() {int arr[] = {1, 2, 3, 4, 5};int size = sizeof(arr) / sizeof(arr[0]);printf("Sum = %d
", sumArray(arr, size)); // 输出: Sum = 15return 0;
}

这里，除了几个固定大小的变量（如 sum 和循环计数器 i）外，没有使用额外的内存。但是，由于我们假设数组本身占用的空间也计入空间复杂度（尽管它是作为输入提供的），所以整个程序的空间复杂度可以视为 O(n)（其中 n 是数组的大小）。然而，仅就 sumArray 函数而言，其额外使用的空间仍然是 O(1)。

3.多项式空间复杂度 O(n^k)（k为常数）
  • 算法所需的额外空间与输入规模的幂次关系成正比。例如，某些嵌套循环算法可能需要二维数组，导致空间复杂度为O(n^2)。这类算法的空间需求随着输入规模的增加而迅速增长。

例如，打印一个 n×n 矩阵的元素：

#include <stdio.h>void printMatrix(int matrix[][10], int n) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {printf("%d ", matrix[i][j]);}printf("
");}
}int main() {int matrix[10][10] = { /* 初始化矩阵 */ };// 假设矩阵已经以某种方式被填充printMatrix(matrix, 10); // 这里 n 被硬编码为 10，但一般情况下可以是任何正整数return 0;
}

注意：

  • 在这个例子中，我为了简化而假设矩阵的第二维大小为常量 10（这是不常见的做法，通常我们会让两个维度都是可变的）。在实际应用中，更常见的做法是声明一个完全可变的二维数组或使用动态内存分配。即使这样，如果我们考虑矩阵本身所占用的空间，那么空间复杂度仍然是 O(n^2)。
4. 动态分配的内存（可变空间复杂度）

当使用 malloc、calloc 或 realloc 等函数动态分配内存时，空间复杂度可能变得不那么直观。它取决于运行时决定分配的内存量。例如：

#include <stdio.h>
#include <stdlib.h>void createAndFillArray(int **array, int size) {*array = (int *)malloc(size * sizeof(int));if (*array == NULL) {fprintf(stderr, "Memory allocation failed
");exit(EXIT_FAILURE);}for (int i = 0; i < size; i++) {(*array)[i] = i * i; // 例如，用平方值填充数组}
}int main() {int size = 100; // 可以根据需要改变大小int *array = NULL;createAndFillArray(&array, size);// 使用数组...free(array); // 不要忘记释放分配的内存！return 0;
}

在这个例子中，createAndFillArray 函数根据传入的 size 参数动态分配一个整数数组。因此，该函数的空间复杂度是 O(size)，即 O(n)（如果我们将 size 视为输入 n参数）。注意，这里的空间复杂度是指除了输入参数和固定大小的变量之外额外分配的内存量。

（3）空间复杂度的分析方法

分析算法的空间复杂度时，需要考虑以下几个方面：

  • 输入输出数据所占用的存储空间：这是由要解决的问题决定的，不随算法的不同而改变。
  • 算法在运行过程中临时占用的存储空间：这是随算法的不同而异的，也是空间复杂度分析的重点。需要关注算法在执行过程中是否需要额外的辅助空间，以及这些空间的增长情况。

综上所述：

  • 空间复杂度是衡量算法内存效率的重要指标之一。通过了解不同类型的空间复杂度及其特点和分析方法，可以选择最合适的算法来解决特定问题，从而提高系统性能。

三 空间复杂度与时间复杂度的关系

  • 时间复杂度和空间复杂度是算法的两个主要性能指标，它们之间存在一定的权衡关系。有时为了追求较好的时间复杂度，可能会牺牲一定的空间复杂度；反之亦然。因此，在设计算法时需要根据具体问题的需求和资源限制进行综合考虑。

四 常见算法的复杂度分析

1. 线性搜索

  • 线性搜索是一种简单的查找算法，它逐个检查列表中的元素，直到找到目标值或遍历完整个列表。

代码展示：

 
#include <stdio.h>int linearSearch(int arr[], int size, int target) {for (int i = 0; i < size; i++) {if (arr[i] == target) {return i; // 找到目标值，返回索引}}return -1; // 未找到目标值，返回-1
}int main() {int arr[] = {2, 4, 6, 8, 10};int target = 6;int result = linearSearch(arr, 5, target);if (result != -1) {printf("Element found at index %d
", result);} else {printf("Element not found in the array
");}return 0;
}

  • 时间复杂度：O(n)
    在最坏情况下，需要比较n次才能找到目标值或确定其不存在。因此，线性搜索的时间复杂度为O(n)。

  • 空间复杂度：O(1)
    除了输入数组和几个辅助变量外，不需要额外的存储空间。因此，空间复杂度为O(1)。

2. 二分搜索

  • 二分搜索要求输入数组是有序的，它通过不断将搜索范围减半来快速定位目标值。

代码展示：

 
#include <stdio.h>int binarySearch(int arr[], int size, int target) {int left = 0, right = size - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标值，返回索引} else if (arr[mid] < target) {left = mid + 1; // 在右半部分继续搜索} else {right = mid - 1; // 在左半部分继续搜索}}return -1; // 未找到目标值，返回-1
}int main() {int arr[] = {2, 4, 6, 8, 10};int target = 6;int result = binarySearch(arr, 5, target);if (result != -1) {printf("Element found at index %d
", result);} else {printf("Element not found in the array
");}return 0;
}

  • 时间复杂度：O(log n)
    每次迭代都将搜索范围减半，因此二分搜索的时间复杂度为O(log n)，其中n是数组的大小。

  • 空间复杂度：O(1)
    同样地，除了输入数组和几个辅助变量外，不需要额外的存储空间。因此，空间复杂度为O(1)。

3. 冒泡排序

冒泡排序是一种简单的排序算法，通过重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止。

#include <stdio.h>void bubbleSort(int arr[], int size) {for (int i = 0; i < size - 1; i++) {for (int j = 0; j < size - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换arr[j]和arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("
");
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int size = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, size);printf("Sorted array: 
");printArray(arr, size);return 0;
}

  • 时间复杂度：O(n^2)
    在最坏情况下，需要进行n*(n-1)/2次比较和可能的交换操作，因此冒泡排序的时间复杂度为O(n^2)。

  • 空间复杂度：O(1)
    冒泡排序是原地排序算法，不需要额外的存储空间。因此，空间复杂度为O(1)。

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！


http://www.ppmy.cn/news/1556320.html

相关文章

梳理你的思路(从OOP到架构设计)_认识EIT造形与内涵

梳理你的思路(从OOP到架构设计)_认识EIT造形与内涵

目录 1、 认识类(Class)与内涵 2、 认识EIT造形与内涵 EIT造形&#xff1a; 类造形的组合​编辑 复习EIT的基本形与变形​编辑 不同内涵 EIT造形 1、 认识类(Class)与内涵 回顾 类(Class)是比较小的造形 各种不同内涵&#xff0c;可以透过类(Class)的形式(Form)来呈现出…
阅读更多...
【ETCD】ETCD 架构揭秘：内部各组件概览

【ETCD】ETCD 架构揭秘：内部各组件概览

ETCD 的主要组件及它们之间的关联关系如下&#xff1a; 目录 1. Client&#xff08;客户端&#xff09;2. gRPC 接口3. Etcd Server Main Loop&#xff08;ETCD 主循环&#xff09;4. Raft&#xff08;共识模块&#xff09;5. Peer Etcd Nodes&#xff08;ETCD 集群节点&#x…
阅读更多...
（教程）如何在HTML网页里嵌入PDF文件？

（教程）如何在HTML网页里嵌入PDF文件？

开发者可以使用不同的标签在 HTML 中嵌入 PDF 文件&#xff0c;常见的有 <embed>、<object> 和 <iframe>。它们都能在网页应用中显示 PDF&#xff0c;但哪种方式更好&#xff1f;有没有比这更好的方式来在浏览器中显示 PDF&#xff1f; 方法 1&#xff1a;使…
阅读更多...
C#轻松实现Winform监控文件夹变化以及监控文件新增、修改、删除、重命名等操作保姆级详细教程

C#轻松实现Winform监控文件夹变化以及监控文件新增、修改、删除、重命名等操作保姆级详细教程

文章目录 一、前言二、FileSystemWatcher 类三、FolderBrowserDialog 类四、具体操作1.设置监听文件夹2.订阅变更事件3.注意事项 一、前言 在开发应用程序时&#xff0c;我们可能会因为场景的需要&#xff0c;要对文件系统中的文件或文件夹进行实时监测&#xff0c;以便在文件…
阅读更多...
NFT市场回暖：蓝筹项目成为复苏主力，空投潮助推价格上涨

NFT市场回暖：蓝筹项目成为复苏主力，空投潮助推价格上涨

随着2024年临近&#xff0c;NFT市场展现出强劲的回暖迹象。多个头部NFT项目公布了代币发行计划&#xff0c;并且随之而来的一波空投潮让市场活力再现。Magic Eden、Pudgy Penguins等项目的动向&#xff0c;成为了推动NFT市场复苏的重要力量。通过空投、代币生成事件&#xff08…
阅读更多...
ES-IndexTemplate和DynamicTemplate

ES-IndexTemplate和DynamicTemplate

IndexTemplate 什么是IndexTemplate 索引模板&#xff0c;帮助你设定Mappings和Settings&#xff0c;并按照一定的规则&#xff0c;自动匹配到新创建的索引之上 模板仅在一个索引被新建的时候&#xff0c;才会产生应用&#xff0c;索引被修改不会影响已创建的索引可以设定多…
阅读更多...
Maven 生命周期

Maven 生命周期

文章目录 Maven 生命周期- Clean 生命周期- Build 生命周期- Site 生命周期 Maven 生命周期 Maven 有以下三个标准的生命周期&#xff1a; Clean 生命周期&#xff1a; clean&#xff1a;删除目标目录中的编译输出文件。这通常是在构建之前执行的&#xff0c;以确保项目从一个…
阅读更多...
单片机STM32、GD32、ESP32开发板的差异和应用场景

单片机STM32、GD32、ESP32开发板的差异和应用场景

STM32&#xff1a;意法半导体在 2007 年 6 月 11 日发布的产品&#xff0c;32位单片机。 GD32&#xff1a;兆易创新 2013 年发布的产品&#xff0c;在芯片开发、配置、命名上基本模仿 STM32&#xff0c;甚至 GPIO 和 STM32 都是 pin to pin 的&#xff0c;封装不改焊上去直接用…
阅读更多...
最新文章

Copyright @ 2022~2023