LeetCode刷题前必须要知道的时间复杂度

青旅半醒 2022-12-02 12:24 213阅读 0赞

LeetCode经常需要优化时间复杂度，在互联网面试的过程中也经常被问到。看完视频[清华计算机博士带你学习Python算法+数据结构][Python]之后，感觉以下几点讲的挺好的，故记录下：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]  
原因：强调的是大概的时间，不是精确的时间

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 3]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 4]

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

### 代码感受一下： ###

在同一个工程文件下创建两个py文件，文件名分别为：cal\_time.py、main.py，比较线性查找与二分查找的时间复杂度：

**main.py**

from cal_time import *
    
    @cal_time
    def Linera_search(nums, value):
        for index, num in enumerate(nums):
           if num == value:
               return index
        else:
            return None
            
        
    @cal_time
    def binary_search(nums, value):
        left = 0
        right = len(nums)-1
        while left <= right:
            mid = (left + right)//2
            if value == nums[mid]:
                return mid
            elif value > nums[mid]:
                left = mid + 1
            elif value < nums[mid]:
                right = mid - 1
        else:
            return None
    
    nums = list(range(100000))
    value = 3000
    Linera_search(nums, value)
    binary_search(nums, value)

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

**cal\_time.py**

import time
    
    def cal_time(func):
        def wrapper(*args, **kwargs):
            t1 = time.time()
            result = func(*args, **kwargs)
            t2 = time.time()
            print("%s running time:%s secs." %(func.__name__, t2 - t1))
            return result
        
        return wrapper

[Python]: https://www.bilibili.com/video/BV1mp4y1D7UP?p=4
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/037935ede0174b2ea3f31ea7f077042d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/5ca249805a104397886395cd23058875.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/3e5122eb4b8143fc93a8b03b98300518.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/3d777d51ae114fa5a23ef2e44c2deaf4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/2cc915218c0a4bda97ba5377c83b81e9.png