【数据结构与算法——C语言版】1.数据结构与算法简介-创新互联

概念

数据结构：“一组数据的存储结构”
算法：“操作数据的一组方法”
数据结构是为算法服务的，算法是要作用再特定的数据结构上的。

公司主营业务：成都做网站、网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出简阳免费做网站回馈大家。

简言之，在编程实践中，我们可能遇到各种各样的场景，比如在1亿个ip地址中判定某个ip是否存在，再比如判断一串用户输入是否符合规定的语法等等。每个场景都有其适用的算法和数据结构，一种问题的解法可能不止一种，解法不同，使用的数据结构与算法就不同，从而不同程序的影响解法的执行效率。
因此，数据结构与算法的核心在于合理选择数据结构，基于算法解决既定场景下的问题。

分类

常见的数据结构与算法有如下几种

数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树
算法： 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

本专栏将用C语言描述常见的数据结构与算法，在阅读本专栏时，请记住一个核心点：量变产生质变，不是所有人天生就是学习程序的天才，第一次问题就知道解法的人毕竟是少数，只有长期的编程积累才能练就快速解决问题的能力，将数据结构与算法内化为功。

时间复杂度和空间复杂度

在以后的文章中，会经常提及时间复杂度和空间复杂度这两个概念，所以这里先对其做一个解释。
时间复杂度与空间复杂度被用来评估一个算法的好坏。

时间复杂度：即算法执行消耗多长时间
空间复杂度：即算法执行需要多少内存

表示 —— 大O的线性表示法

推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

比如

for (int i = 0; i< n; ++i) {for (int j = 0; j< n; ++j) {//xxx
	}
}

该代码写了两层循环，每个循环执行n次，所以可以称为总共执行 n*n 次，也就是 n²，用大O表示法，就是该代码的时间复杂度为 O(n²)
该代码只使用了 i 、 j 、 n 三个变量，是一个可数的数字，所以空间复杂度为 O(1)
同理，下面这段代码的时间复杂度和空间复杂度是多少呢？

int nums[6] = {0};
for (int i = 0; i< 6; ++i) {printf("%d\n", nums[i]);
}

答案为：时间复杂度O(1)，空间复杂度O(1)；
为什么这里明明有一个循环但时间复杂度却是O(1)？明明有一个数组空间复杂度也是O(1)？
注意： 时间复杂度和空间复杂度只计算不可量化的值，而nums[6]定义了一个有6个元素的数组，是可量化的；for 循环也只是循环了 6 次，也是可量化的。所以时空复杂度都为O(1)

时间复杂度分析举例 举例1

void func(int N, int M) 
{int count = 0;
    for (int k = 0; k< M; ++k) 
    {++count;
    }
    for (int k = 0; k< N; ++k) 
    {++count;
    }
}

时间复杂度：O(M*N)
空间复杂度：O(1)

举例2

int n;
scanf("%d", &n);
int *a = (int*)malloc(sizeof(int) * n);
memset(a, 0, sizeof(int) * n);

时间复杂度：O(1)
空间复杂度：O(n)
库函数的时空复杂度不计算在内

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站栏目：【数据结构与算法——C语言版】1.数据结构与算法简介-创新互联
分享URL：http://mswzjz.cn/article/diidsd.html