算法概述-知识总结 算法概念 算法：使用程序解决问题的方法。 数据结构：数据的组织及操作方式。
算法描述 描述方式 自然语言描述 流程图描述 伪代码描述
算法描述示例 问题： 如何判断一个数n是奇数还是偶数？
自然语言描述： ①把这个数整除2，对余数进行判断 ②如果余数是0，则为偶数 ③如果余数是1，则为奇数
流程图描述：
伪代码描述： IF n % 2 == 0 THEN 输出偶数 ELSE 输出奇数
算法评价 算法评价方式 正确性 未定型 可扩展性 时间复杂度 空间复杂度
时间复杂度 时间复杂度描述算法执行所需要的步骤数或操作数： 使用大O表示法描述 若复杂度和数据大小相关则使用n表示数据大小
常见算法时间复杂度：
复杂度
运算次数
时间复杂度描述
数据规模
O(1)
常数次
常数时间复杂度
无限制
O(logn)
logn
对数时间复杂度
n<2^100000000
O(n)
n次
线性时间复杂度
n<100000000
O(nlogn)
nlogn
线性对数时间复杂度
n<5000000
O(n2)
n^2
平方时间复杂度
n<10000
O(n3)
n^3
立方时间复杂度
n<500
O(nk)
n^k
k次方时间复杂度
n<100
O(2n)
2^n
指数时间复杂度
n<26
空间复杂度 空间复杂度描述算法执行过程中临时占用存储空间的大小： 使用大O表示法描述 若复杂度和数据大小相关则使用n表示数据大小
错误的题目要弄懂，不会的千万要来问老师⚠️
总结作业非常重要，请务必认真完成✔️
算法概述--选择题 一个算法可以用不同的形式来描述，但要求描述比较规范，因此不能用自然语言描述 A. 正确 B. 错误
算法不适合用以下哪种形式来描述： A. 伪代码 B. 流程图 C. 自然语言 D. HTML语言
时间复杂度和空间复杂度是评价算法的两个常见维度 A. 正确 B. 错误
在评价算法的维度中，时间复杂度比空间复杂度更重要 A. 正确 B. 错误
通常情况下，下列哪个式子所代表的时间复杂度最高 A. O(1) B. O(n) C. O(nlogn) D. O(n²)
数据结构对于算法的执行效率没有影响 A. 正确 B. 错误
信奥竞赛中要求程序的执行时间小于1秒，考试所用电脑为普通微型电脑。因此，对于一个时间复杂度为O(n)的算法，如果输入数据项规模达到10⁹时，会导致程序运行超时 A. 正确 B. 错误
信奥竞赛中要求程序的执行时间小于1秒，考试所用电脑为普通微型电脑。如果输入数据项规模最大为10⁵，下列哪个时间复杂度的算法不会超时 A. O(n²) B. O(n³) C. O(2ⁿ) D. O(n㏒n)
信奥竞赛中要求程序的内存使用小于512M。因此，如果我们的程序的空间复杂度为O(n)，且我们需要把每个输入项存储到一个int类型中，那么程序可以处理的最大数据规模是10⁹ A. 正确 B. 错误
下列说法错误的是 A. 算法描述了解决问题的步骤和规则 B. 数据结构描述了数据的组织和存储方式 C. 选择合适的数据结构可以使算法更高效 D. 所有的算法都是稳定的
算法概述--选择题答案 B 解析：自然语言可以用来描述算法 D 解析：HTML是适合浏览器展现的标记语言，会增加冗余信息用于界面展现，不适合描述算法 A 解析：这两个复杂度是评价算法性能的两个核心维度。时间复杂度关注算法的执行速度，而空间复杂度关注算法的内存使用效率。 B 解析：两者的重要性没有固定的优先级。 D 解析：简单的比较复杂度的方式取一个足够大的特值，例如n=10，来比较不同的不同复杂度的大小 B 解析：算法的执行效率通常通过时间复杂度和空间复杂度来衡量。时间复杂度反映了算法执行所需时间的增长趋势，而空间复杂度反映了算法执行过程中所需的存储空间大小。 A 解析：对于O(n)算法，1s能够处理的数据规模在10的8次方大小， D 解析：对于A选项O(n²)算法，10的五次方的数据规模可以折算成O(n)处理10的10次方，时间会显著超过1秒，因此A选项不行，而B、C的复杂度高于A。对于 O(n㏒n)的算法，可以处理的数据集小于10的6次方 B 解析：512MB = 51210241024个字节， 一个int为4个字节，所以512MB能够存储的int数组长度大概在10的八次方量级，10的九次方的数据规模会超过512MB的限制
解析：D 并不是所有的算法都是稳定的，在排序算法中将会具体介绍
