目录

一、数据结构与算法

二、时间复杂度

三、空间复杂度

四、小结

---

一、数据结构与算法

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构分为：逻辑结构和物理结构

逻辑结构：集合结构、线性结构、树形结构和图形结构；

物理结构：顺序结构和链式结构。

算法：实现某种功能的代码。

算法的特性：输入、输出、有穷性、确定性和可行性。

算法的设计要求：正确性、可读性、健壮性、时间效率高和存储量低。

程序：数据结构+算法

二、时间复杂度

在给大家介绍时间复杂度之前，大家可以先回想一下高中数学里面学习的初等函数的知识。

按照增长趋势从小到大排序：

常数函数<对数函数<一次函数<二次函数<三次函数<指数函数<阶乘函数<幂指函数。

时间复杂度：衡量算法执行时间随输入规模增长的变化趋势，用大O来表示。

以从1一致累加到100的和的代码来举例

package Algorithm

main(): Int64 {
    // for循环
    var sum = 0
    for (i in 1..=100) {
        sum += i
    }
    println(sum)
    return 0
}

上述代码：执行次数是由for循环中，由区间上限的值来决定，这里是100，因此，如果用函数来表示这段代码的时间复杂度就是f(x) = 1 + x + 1，此时 x=100，f(x)=102，用大O表示法，则为O(x)，由于在时间复杂度里，习惯用n来表示自变量，为此该代码官方的时间复杂度表示为O(n)。

同样的，实现上述代码的功能，我们还可以借鉴等差数列求和公式

package Algorithm

main(): Int64 {
    let sum = (1 + 100) * 100 / 2
    println(sum)
    return 0
}

此时，该代码的时间复杂度函数就是f(x) = 2，官方的时间复杂度为：O(2)。

这两段代码作比较来看，无论从代码量上，还是从时间复杂度函数的增长趋势来看，常数函数的效率要远低于一次函数；因此，虽然都是实现从1累加到100的代码，很明显第二个代码的算法更好。

注意：在时间复杂度的表示里，我们是舍小项、舍系数，只保留最大项即可。

然而，并非所有代码都可以计算出运行次数

package Algorithm

main(): Int64 {
    let n = 10
    var i = 1
    while (i <= n) {
        i = i * 2
    }
    println(i)
    return 0
}

这段代码的执行次数，却决于n的大小，加入我们不知道n的取值情况下，如何计算这段代码的运行次数，我们可以设：这段代码的运行次数为x，则有，解得：，这时，该代码的时间复杂度为O(logn)。

三、空间复杂度

类似于时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度的计算公式为S(n) = O(f(n))，其中n表示问题的规模，f(n)表示关于n所占存储空间的函数。

在现代编程中，随着计算机的存储空间越来越大，在一般的业务场景里，通常会选择用空间来换取时间，只有极少数的需求会用时间换空间，这里所提到的“时间”和“空间”，就是时间复杂度和空间复杂度。为此，为了避免后续因为“偷懒”而直接描述“复杂度”的概念，通常情况下，都指的是时间复杂度。

四、小结

本章为大家详细的介绍了仓颉数据结构与算法中时空复杂度的内容，下一章，为大家带来常见排序算法的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！