第2章算法复杂度2025/6/101主要内容●算法●算法的复杂度●常见的复杂度
2.1算法算法(algorithm)就是一个正确的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。2025/6/102
2025/6/103算法的4个主要特性：2.1算法算法的4个主要特性是：●确切性：算法由语句组成，每个语句的功能是确切的。●输入数据：可以向算法输入多个或0个数据（方法可以有参数或无参数），即算法可以接收或不接收外部数据。●输出数据：算法可以给出明确的计算结果（方法的返回值）或输出若干数据到客户端以反映算法产生的效果。●可行性：基本操作都是在有限时间内被完成。所谓有限时间是指这个时值仅仅依赖于特定的硬件设施，不依赖于一个正整数n，即不会随着n的增加而增大。●确切性●输入数据●输出数据●可行性
2025/6/104一个算法不能在有限的时间内结束，就不属于算法复杂度的研究的范畴，比如一个算法里出现的无限循环，就不再属于算法复杂度的研究的范畴了2.2复杂度算法，从执行到结束，涉及两个度量：一个是执行方法所消耗的时间，一个是执行方法所需要的内存空间。
2025/6/105方法里声明的局部变量，包括参数都不归类到基本操作，即不是基本操作。2.2复杂度⒈基本操作一个基本操作是一个语句或一个运算表达式。一个基本操作是一条语句或一个运算表达式，而且必须是在有限时间内能被完成的计算步骤，其耗时仅仅依赖于特定的硬件设施，不依赖于一个正整数n，不会随着n的增加而增大。
2025/6/106在计算算法执行的基本操作的总数时，要真对最坏的情况，即在某种条件下执行的基本操作的总数是最多的情况2.2复杂度3时间复杂度算法执行的基本操作的总数T(n)。算法的复杂度主要是度量随着n的增大，T(n)值的趋势。
2025/6/107学习复杂度，记住一个通俗的道理：时间累加，空间不累加.2.2复杂度4复杂度比较
2025/6/1082.3常见复杂度⒈O(1)复杂度算法中的基本操作被执行的总次数是一个常量，即不依赖一个正整数n、不会随着n的增加而增大，那么将算法的时间复杂度，记作O(1)。算法中的所占用的内存是一个常量，即所占内存不依赖一个正整数n、不会随着n的增加而增大，那么将算法的空间复杂度，记作O(1)。?例子1计算最大值ALG2_1.pych2_1.py
2025/6/1092.3常见复杂度1.O(1)复杂度?sum()函数中return语句被执行了一次，range(1,101)被重复执行了101次，赋值语句“sum_result+=i;”重复了100次。那么算法中的基本操作被执行的总数是202，是一个常量，因此时间复杂度是O(1)。sum()函数中有两个局部变量sum_result和i，而两个变量占用内存的大小都是固定的，因此空间复杂度是O(1).?ALG2_2.pych2_2.py
2025/6/10102.3常见复杂度2.O(n)复杂度?
2025/6/10112.3常见复杂度2.O(n)复杂度?ALG2_3.pych2_3.py?
2025/6/10122.3常见复杂度2.O(n)复杂度例子4求数组元素的最大值ALG2_4.pych2_4.py?
2025/6/10132.3常见复杂度2.O(n)复杂度例子5寻找缺失的一个自然数ALG2_5.pych2_5.py例子5寻找缺失的一个自然数?
2025/6/10142.3常见复杂度2.O(n)复杂度例子5?find_missing_number(inta[],intlength)算法中的基本操作不是加法和减法，而是使用了异或^运算。?find_number(arr,length)的算法和前面两者不同，算法使用的是穷举法，算法中的for语句里嵌套了for语句形成的双层循环，不难验证其时间复杂度是O(n^2)。ALG2_5.py
2025/6/10152.3常见复杂度3.
2025/6/10162.3常见复杂度3.?ALG2_6.pych2_6.py?
2025/6/10172.3常见复杂度3.例子7起泡法排序ALG2_7.pych2_7.py
2025/6/10182.3常见复杂度4.???
2025/6/10192.3常见复杂度4.例子8ALG2_8.pych2_8.py???
2025/6/10202.3常见复杂度5.???
2025/6/10212.3常见复杂度5.例子9二分法ALG2_9.pych2_9.py????
2025/6/10222.3常见复杂度5.例子10欧几里得算法ALG2_10.pych2_10.py????
2