图解算法—大O表示法

2024-08-24 17:32

文章标签 算法图解表示法

本文主要是介绍图解算法—大O表示法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 时间复杂度（大O表示法）
- - 图解大O表示法
  - - 算法1
    - 算法2
  - 一些常见的大O运行时间
  - 下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间
  - 总结

时间复杂度（大O表示法）

我们在运行算法时，仅仅知道算法需要多长时间能运行完还不够，还需要知道运行时间如何随列表增长而增加，这就是大O表示法的用武之地。大O表示法指出了算法有多快。例如，假设列表包含n个元素，简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O（n）。注：大O表示法指的并非以秒为单位的速度，而是在最坏情况下算法需要执行的操作数。

图解大O表示法

假设我们要画一个网格，它包含16个格子
在这里插入图片描述

算法1

以每次画一个的方式画16个格子。画一个格子是一次操作，需要画16个格子就需要16步，所以该算法的运行时间为O（n）
在这里插入图片描述

算法2

每次将纸对折。对折一次就是一次操作，每折一次，格子数就翻倍，折4次就能得到16个格子。所以该算法的运行时间为O（log n）.
在这里插入图片描述

一些常见的大O运行时间

下面按从快到慢的顺序列出了5种大O运行时间
O（log n）,也叫对数时间，这样的算法包括二分查找；
O（n）,也叫线性时间，这样的算法包括简单查找；
O（n*log n）,这样的算法包括快速排序（一种速度较快的排序算法）；
O（n^2）,这样的算法包括选择排序（一种速度较慢的排序算法）；
O（n!）,这样的算法包括旅行商问题（一种非常慢的算法）。