Day: 2021年12月5日

算法分析—大O、大Ω、大θ

admin 编程 暂无评论 276 浏览

前言

在算法的学习中，最开始便是要学习算法的分析。学习算法分析时，我们便会接触到这么几个符号：大O、大Ω、大θ，常常让人难以理解。

在通常的算法分析时，我们可以明白，在输入规模较小，各种算法之间的时间消耗并无明显差别。只有当输入规模较大时，对各个算法之间消耗差别的对比与分析才有意义。所以上面几个符号便常用于表达当规模逐渐趋向于一个极大数时的算法复杂度。

在表示一个算法时间复杂度时，我们常用如 T(n)=O(n^2) 的形式表示，而在渐进分析中的 “=” 更倾向于 “∈” 的意思。打个比方：渐进表达式 f(n) = O(g(n)) 所表达的意思是 O(g(n)) = [ f(n),h(n),…,g(n) ], f(n) ∈ O(g(n)) 。

一、大O表示法

f(x) = O(g(x)) 表示的含义是f(x)以g(x)为上界

大O是我们在分析算法复杂度时最常用的一种表示法。当函数的大小只有上界，没有明确下界的时候，则可以使用大O表示法，该渐进描述符一般用与描述算法的 最坏复杂度。f(x) = O(g(x))正式的数学定义：存在正常数c、n、n0，当 n>n0 的时，任意的

…
Read more

算法中的大O表示法

admin 编程 暂无评论 98 浏览

算法中的大O表示法

1.算法概念

计算机科学中的算法指的就是计算机执行的指令。

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。

一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

               -----------       
      输入 --> |   算法    | --> 输出
               -----------

算法的核心是创建问题抽象的模型和明确求解目标，之后可以根据具体的问题选择不同的模式和方法完成算法的设计。

2. 时间复杂度

算法的时间复杂度是指算法需要消耗的时间资源。

一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做：

T(n) = O(f(n))

算法执行时间的增长率与f(n) 的增长率正相关，称作渐近时间复杂度（Asymptotic Time Complexity），简称时间复杂度。

3. 空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。

其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。

同时间复杂度相比，空间复杂度的分析要简单得多。

4. 大 O 表示法

…
Read more