算法笔记(八):复杂度分析(二)

#感兴趣的可以去订阅极客时间前谷歌工程师的专栏:数据结构与算法之美,个人觉得写的很不错。这里只是我自己做的一个简单的笔记

(一) 对数阶时间复杂度

1 def tset(n):
2     i = 1
3     while i <= n:
4         i = i*2

上面这段代码,i 从1开始,循环一次乘于2,当大于n时,循环结束,我们可以得到2x = n。要计算上面这段代码的时间复杂度,求解x的值就行了,根据数学基础中和对数相关的计算,可以得到x = log2n = logn,所以这段代码的时间复杂度就是O(logn)。

        将代码修改成下面这样,很容易计算出,代码的时间复杂度是O(log3n)。

1 def tset(n):
2     i = 1
3     while i <= n:
4         i = i*3

        在对数中log3n = log32*log2n,所以O(log3n) = O(log32*log2n) = O(C*log2n),其中C是常量,根据渐进符号的定义,计算时间复杂度时,我们可以忽略常量,所以上面这段代码的时间复杂度也是O(logn),同理,所有对数阶时间复杂度的表示中,可以同一表示为O(logn)。

   如果一段代码的时间复杂度是O(logn),如果循环运行n次,那么时间复杂度就是O(nlogn)。

(二) 空间复杂度

  下面这段代码,和分析时间复杂度一样,因为只有第三行代码创建了一个大小为n的数组,其他不是常量就是不占用内存空间,所以这段代码的时间复杂度是O(n)

1 def test1(n):
2     a = 0
3     arr = numpy.arange(n)
4     for i in range(n):
5         arr[i] = i*i
6     return arr

(三)  最好、最坏、平均时间复杂度

 这里我们用之前线性查找的例子:

1 import numpy as np
2 
3 #找到结果,返回索引,否则返回None
4 def search(array,key):
5     for j in range(len(array)):
6         if array[j] == key:
7             return j
8     return None

最好时间复杂度: 如果第一个元素就是我们要查找的元素,那么代码的时间复杂度就是O(1)

最坏时间复杂度:如果最后一个元素才是我们要查找的元素,或者数组中根本就没有我们要查找的元素,那么代码的时间复杂度就是O(n)

平均时间复杂度:查找元素在是否在数组中有2种情况,在数组中(0...n-1)和不在数组中,那么总共就有 n+1种情况,我们将需要查找的元素(可能运行的次数,第n个元素和不在数组中运行次数都是n次)相加除以n+1就可以得到代码的时间复杂度。

(1+2+3...+n+n)/ (n+1) = (n*(n+2))/2(n+1),那么平均时间复杂度为O(n)。

1+2+3...+n  可以推导出公式 n(n+1)/2,详细推导过程不明白的可以自己网上查查资料。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SeanCheney的专栏

《Pandas Cookbook》第03章 数据分析入门1. 规划数据分析路线2. 改变数据类型,降低内存消耗3. 从最大中选择最小4. 通过排序选取每组的最大值5. 用sort_values复现nl

15920
来自专栏chenjx85的技术专栏

leetcode-58-Length of Last Word

21960
来自专栏算法修养

PAT 1012 数字分类 (20)

给定一系列正整数,请按要求对数字进行分类,并输出以下5个数字: A1 = 能被5整除的数字中所有偶数的和; A2 = 将被5除后余1的数字按给出顺序进行交错...

27350
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第4章 NumPy基础:数组和矢量计算4.1 NumPy的ndarray:一种多维数组对象4.2 通用函数:快速的元素级数组函数4.3 利用数组进行数据处理4.

NumPy(Numerical Python的简称)是Python数值计算最重要的基础包。大多数提供科学计算的包都是用NumPy的数组作为构建基础。 NumPy...

47180
来自专栏ACM算法日常

基础算法|7 希尔排序 HDU 1425

我们从最初的冒泡排序算法,到上篇文章的折半插入排序算法,我们一共学习了5种排序算法,相信以大家的聪明才智肯定都消化了^_^。在本篇文章中,我们又将学习第6种排序...

9720
来自专栏数据结构与算法

P3709 大爷的字符串题(50分)

题目背景 在那遥远的西南有一所学校 /*被和谐部分*/ 然后去参加该省省选虐场 然后某蒟蒻不会做,所以也出了一个字符串题: 题目描述 给你一个字符串a,每次询问...

35270
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 适合大规模的数据排序 数据结构与算法学习笔记之如何分析一个排序算法?

在数据排序的算法中,不同数据规模应当使用合适的排序算法才能达到最好的效果,如小规模的数据排序,可以使用冒泡排序、插入排序,选择排序,他们的时间复杂度都为O(n...

10240
来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(6) - 插入排序

19650
来自专栏目标检测和深度学习

常用排序算法总结(1)

14220
来自专栏海天一树

AtCoder入门练习题B--题解报告

一、题目 https://practice.contest.atcoder.jp/tasks/practice_2 二、分析 这里有三组测试用例。 第一组N =...

33180

扫码关注云+社区

领取腾讯云代金券