[Python算法学习Day2] 1.3大O表示法

yanghongchen666

1.3.1 算法的运行时间一不同的速度增加
    大O表示法指出了算法有多快。例如，假设列表包含n 个元素。简单查找需要检查每个元素，因此需要执行n 次操作。
    大O表示法让你能够比较操作数，它指出了算法运行时间的增速
    大o表达法: O(n)  括号里面的n是代表操作数

1.3.2 理解不同的大O运行时间
    举例:
        如果要在一张纸上画16个格子有两种算法
            第一种: 拿笔画16个，每次画格子算作一个操作数，用大O表示法也就是O(16)
            第二种: 将纸对折四次，每次对折算一做一个操作数,用大O表示法也就是O(4),显而易见第二种算法更快

1.3.3大O表示法指出了最糟糕情况下的运行时间
    举例:
        如果你在电话簿中寻找Adit这个人，如果一次找到运行时间其实还是O(n),因为大O表示法说的是最糟糕的情况

1.3.4一些常见的大O运行时间
    O (log n )也叫对数时间 ，这样的算法包括二分查找。
    O (n )也叫线性时间 ，这样的算法包括简单查找。
    O (n * log n )这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
    O (n^2)这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
    O (n !)这样的算法包括接下来将介绍的旅行商问题的解决方案
    ——一种非常慢的算法。

练习:

1.3 在电话簿中根据名字查找电话号码
    O(log n)

1.4 在电话簿中根据电话号码找人（提示:你必须查找整个电话簿）
    O(n)

1.5 阅读电话簿中每个人的电话号码
    O(n)

1.6阅读电话簿中姓名以A打头的人的电话号码。这个问题比较棘手， 它涉及第4章的概 念。答案可能让你感到惊讶！
    O(n)


1.3.5 旅商问题
是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。
问题内容为“给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路



1.4总结:
    1.二分查找的速度比简单查找要快很多
    2.O(log n) 比 O(n)快 需要搜索的元素越多，前者比后者月快的越多
    3. 算法运行时间并不以秒为单位(用毫秒)
    4.算法运行时间是从增速的角度度量的
    5.算法运行时间用大O表示法表示


每日一题Leetcode: 35 Search Insert Position

def search_insert(nums,target):
    low = 0
    high = len(nums) -1 
    
    if target > nums[high]:
        return len(nums)
    
    for i in range(len(nums)):
        if nums[i] >= target:
            return i

lis = [1,6,8,9,10]
print(search_insert(lis,11))

风一样的僧

嘉岳呀

时间复杂度？

那么1.3.2案例两个都是 O(1)

常数去除，如果只有常数，都当作1，也就是说，如果你的循环次数到达了114514次，他的时间复杂度也是O(1)

hornwong

yanghongchen666

嘉岳呀 发表于 2022-10-1 19:03
时间复杂度？

那么1.3.2案例两个都是 O(1)

应该还没研究到时间复杂度哈哈哈哈，第一听刚开始学算法。看书上就是写了按照一个操作数算一次的话这两个例子分别是O(16)跟O(4)

风一样的僧

kerln888

1molHF

wangyanren

路过