【Hello算法】 ＞ 第 1 关 ＞ 初识 算法 与 复杂度分析

———————————————————————————————————————————————————————————-
————————————————————Hello算法—速通笔记—第一集—start———————–———————————————-

What are algorithms and data structures ?-什么是算法与数据结构？

「算法 algorithm」是在有限时间内解决特定问题的一组指令或操作步骤
「数据结构 data structure」是计算机中组织和存储数据的方式
1
2

How to conduct complexity analysis ?-如何进行复杂性分析？

时间效率 和 空间效率 是衡量 算法优劣 的两个主要评价指标。

常见时间复杂度从低到高排列有 O(1) 、O(logn) 、O(n) 、O(nlgn) 、O(n) 、O($n^2$) 和 O(n!) 等。

空间复杂度的作用类似于时间复杂度,常见空间复杂度从低到高排列有 O(1) 、O(logn) 、O(n) 、O(n) 、O($n^2$) 等。
设算法的操作数量是一个关于输入数据大小 n 的函数，记为 T(n) 。

时间复杂度

第一步：统计操作数量

 忽略  T(n)  中的常数项。因为它们都与 n 无关，所以对时间复杂度不产生影响。
 省略所有系数。例如，循环  2n 次、5n+1 次等，都可以简化记为 n 次，因为  n 前面的系数对时间复杂度没有影响。
 循环嵌套时使用乘法。
1
2
3

第二步：判断渐近上界

 时间复杂度由  T(n)  中最高阶的项来决定。这是因为在 n 趋于无穷大时，最高阶的项将发挥主导作用，其他项的影响都可以忽略。
1

空间复杂度

算法在运行过程中使用的内存空间主要包括：
输入空间、暂存空间(用于存储算法在运行过程中的变量、对象、函数上下文等数据)、输出空间 。
一般情况下，空间复杂度的统计范围是“暂存空间”加上“输出空间”。
我们通常统计暂存数据、栈帧空间和输出数据三部分：

第一步：以最差输入数据为准

 当 n < 10 时，空间复杂度为 O(1) ；但当 n > 10 时，初始化的数组 nums 占用 O(n) 空间，因此最差空间复杂度为 O(n) 。
1

第二步：以算法运行中的峰值内存为准

 例如，程序在执行最后一行之前，占用 O(1) 空间；当初始化数组 nums 时，程序占用 O(n) 空间，因此最差空间复杂度为 O(n) 。
1

注：在递归函数中，需要注意统计栈帧空间。

小结Tips：

- 常见的空间复杂度：展示的是空间复杂度，其反映的是增长趋势，而不是占用空间的绝对大小。
- 函数与方法的区别：函数（function）可以被独立执行，所有参数都以显式传递。方法（method）与一个对象关联，被隐式传递给调用它的对象，能够对类的实例中包含的数据进行操作。
- 尾递归函数的空间复杂度通常认为是O(n),只是说可以优化到O(1)。
1
2
3

————————————————————————————————————————————————————————————
—————————————————————Hello算法—速通笔记—第一集—end—————————————————————–—-