yanghongchen666 发表于 2022-10-1 14:19:29

[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))

风一样的僧 发表于 2022-10-1 16:09:33

{:10_254:}

嘉岳呀 发表于 2022-10-1 19:03:42

时间复杂度?

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

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

hornwong 发表于 2022-10-2 00:15:49

{:5_108:}

yanghongchen666 发表于 2022-10-2 03:05:46

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

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


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

风一样的僧 发表于 2022-10-2 08:33:54

{:10_254:}

kerln888 发表于 2022-10-2 08:52:00

{:10_256:}{:10_256:}{:10_256:}

1molHF 发表于 2022-10-2 09:51:03

{:10_256:}

wangyanren 发表于 2022-10-13 11:03:16

路过
页: [1]
查看完整版本: [Python算法学习Day2] 1.3大O表示法