OJ刷题准则，拒绝暴力求解

妖狐艹你老母 2022-11-06 13:59 130阅读 0赞

> 写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我`热爱AI、热爱分享、热爱开源`！ 这博客是我对学习的一点总结与记录。如果您也对 `深度学习、机器视觉、算法、Python、C++` 感兴趣，可以关注我的动态，我们一起学习，一起进步~  
> 我的博客地址为：[【AI 菌】的博客][AI]  
> 我的Github项目地址是：[【AI 菌】的Github][AI _Github]

时间和空间复杂度是算法中很重要的概念，同时在面试中也会经常要求分析代码的时空复杂度。因此，我们在OJ平台上做每一道题时，在思考算法时也应该大致分析一下自己代码的时空复杂度，切勿盲目暴力求解。

在常见的OJ 平台上的题库中，一般都会附带数据范围，为了避免超时，在做题时也要养成习惯：**通过题目给出数据范围，估测可允许的最大时间与空间复杂度量级，进而选择对应的可用算法。**

在估算时，我们可以按照以下的准则：

> 在大部分 C++/Java 平台上，计算机 1s 内的处理次数大约为 10^7 - 10^8，Python 由于相对较慢，大约为 10^6 -10^7，而大部分OJ平台的时限都在 1s - 10s 左右，而对于一些题目来说，时限会更短。

下面举个实际的例子：

题目描述：
    给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
    你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
    要求：返回滑动窗口中的最大值。
    
    示例 ：
    输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
    输出：[3,3,5,5,6,7]
    
    提示：
    1 <= nums.length <= 10e5
    -10e4 <= nums[i] <= 10e4
    1 <= k <= nums.length

注：题目来源力扣

对于本题，在设计算法的时候，我们必须得考虑**提示部分的数据范围**：

*  **确定主要考量对象**。由于我们主要对数组nums进行操作，所以nums.length是重要的考量对象。
 *  按**范围最大值**去估算耗时，在这里取nums.length的最大值10e5。
 *  **设计相应时间复杂度的算法**。想想如果设计的算法时间复杂度为O(n^2)，那么该程序一次最多需要处理10e10次，这将大大超过时限。所以对于本题，应该设计时间复杂度为O(n)或者O(nlogn)的算法。

--------------------

***由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！***

![在这里插入图片描述][2020090613542669.png_pic_center]  
***推荐文章***

[程序员面试必备的八大数据结构][Link 1]

[AI]: https://blog.csdn.net/wjinjie
[AI _Github]: https://github.com/Keyird/DeepLearning-TensorFlow2.0
[2020090613542669.png_pic_center]: /images/20221023/86754ddbfa4445b1bb59a674a2f780a4.png
[Link 1]: https://ai-wx.blog.csdn.net/article/details/114519112