OJ快速入门 | Ziuch の Blog

type

status

date

slug

summary

0 本节配套代码

时间复杂度.ipynb

52.8KB

Google Colaboratory

https://colab.research.google.com/drive/11LvpAiSnjpAjnprw8-7OvTvqefIZi7JD?usp=sharing

1 时间复杂度

💡

时间复杂度就是用来方便开发者估算出程序的运行时间

1.1 大O表示法

💡

代码运行次数的数量级别

以下代码的时间复杂度：O(3+3n^2+2n+1) = O(3n^2+2n+4) = O(n^2)

1.2 举例

1.2.1 O(1)

1.2.2 O(logn)

1.2.3 O(n)

1.2.4 O(n^2)

1.2.5 问以下代码的时间复杂度是多少?(two points)

1.3 各种复杂度比较

💡

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(nlogn)线性对数阶 < O(n^2)平方阶 < O(2^n) (指数阶)

1.4 python内置函数的时间复杂度

python各种内置函数的时间复杂度_Forlogen的博客-CSDN博客_pythonstr函数时间复杂度

python各种内置函数的时间复杂度最近在做题的时候常常遇到题目对于时间复杂度的控制，虽然暴力的方法可以通过OJ，但是这样做并没有达到题目本身的目的。虽然自己代码中循环结构的时间复杂度可以控制，但是却不是很清楚python各种内置函数和各种数据结构的可用方法的时间复杂度，所以查阅相关资料做个总结。 List Set 集合（set）是一个无序的不重复元素序列。可以使用大括号 { } 或者 set() 函数创建集合，注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典。 set内置的各种函数： add()：添加元素 clear()：清空集合 copy()：拷贝一个集合 difference：返回多个集合的差集 difference_update()：移除集合中的元素，该元素在指定的集合也存在 discard(obj)：删除集合中指定的元素 intersection(set1, set2 ...

https://blog.csdn.net/forlogen/article/details/105073343

1.5 递归表达式的时间复杂度计算(主方法/定理)

主方法的一般形式是：

T(n) = aT(n/b) + f(n)

a是递归调用的次数，n/b是递归子问题的规模，f(n)是在分解和合并子问题过程中花费的时间。

根据主方法，可以通过比较f(n)和的大小关系来确定T(n)的时间复杂度：

当f(n) = Θ(n^c)时，

如果c < ，则T(n) = Θ()。

如果c = ，则T(n) = Θ()。

如果c > ，则T(n) = Θ(f(n))。

举例：

递归式：T(n) = 2T(n/2) + n

对于这个递归式，我们可以将其形式转化为上述一般形式：

a = 2, b = 2, f(n) = n

根据上述公式，可以得到：

= = 1

f(n) = n = Θ()

由于f(n) = Θ()，其中c = 1 = ，因此T(n) = Θ(n log n)。

因此，该递归式的时间复杂度为O(n log n)。

2 空间复杂度

💡

用来评估自定义函数或算法内存占用大小

💡

原地工作：额外空间相对于输入数据量来说是常数O(1)

3 数据范围

3.1 确定算法

💡

一般笔试题的时间限制是1秒或2秒，代码执行次数控制在10^7∼10^8

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

3.2 确定数据类型

💡

python自带超长数字，一般只需要判断是整数，小数还是字符串即可，注意小数精度问题

4 黑盒测试原理

💡

LeetCode是如何评判一份代码的正确性的？

💡

只比较标准输出和程序输出

一般有一组input文件和一组output文件，先运行你的程序，同时在后台开始计时，将所有input数据加入输入流中，将程序输出的内容和output文件比对若运行时出错时即执行出错，若在计时器计时结束前你的程序未能结束即超出时间限制，若存在程序输出与标准输出不一致即答案错误，否则答案正确

💡

以下通过代码来简单演示LeetCode的判题机制

5 LeetCode上的常见错误及解决方式

5.1 答案错误

💡

一般来说是某些特殊情况没有考虑到，这个时候可以根据评测给出的错误样例进行代码的模拟，找到代码出错的位置，分析代码出错的原因并加以改正

5.2 超出时间限制

💡

一般来说是算法的时间复杂度太高了，需要根据题目给定的数据范围优化自己的代码，或者更换更为高效的实现方法

5.3 执行出错

💡

一般来说问题是数组越界，或是变量未定义，类型不匹配等问题，具体观察错误信息定位错误的位置