[Python算法学习Day2] 1.3大O表示法
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:
return len(nums)
for i in range(len(nums)):
if nums >= target:
return i
lis =
print(search_insert(lis,11))
{:10_254:} 时间复杂度？
那么1.3.2案例两个都是 O(1)
常数去除，如果只有常数，都当作1，也就是说，如果你的循环次数到达了114514次，他的时间复杂度也是O(1) {:5_108:} 嘉岳呀 发表于 2022-10-1 19:03
时间复杂度？
那么1.3.2案例两个都是 O(1)
应该还没研究到时间复杂度哈哈哈哈，第一听刚开始学算法。看书上就是写了按照一个操作数算一次的话这两个例子分别是O(16)跟O(4){:10_257:} {:10_254:} {:10_256:}{:10_256:}{:10_256:} {:10_256:} 路过
页:
[1]