淘先锋技术网

首页 1 2 3 4 5 6 7

从零开始学习算法,同时记录小编的成长历程,也希望小编的博客能对学习算法的同学给到一点帮助,废话不多说,开始上干货。

目录

 

认识复杂度

在算法当中我们如何判断一个算法的好坏核心标准?

1,时间复杂度(记为O(高价项)保留高价,去掉低价,常熟与系数(低价,高价)流程决定)

2,额外空间复杂度(记为O(n)流程决定)

3,常数项时间(实现代码时细节决定)

4,一个问题的最优解是什么意思?

对数器

1,实现·是对数器?

2,设置随机样本产生器

异或运算


认识复杂度

在算法当中我们如何判断一个算法的好坏核心标准?

通过算法的1,时间复杂度 ,2,额外空间复杂度与3,常数项时间进行判断。

1,时间复杂度(记为O(高价项)保留高价,去掉低价,常熟与系数(低价,高价)流程决定)

  1,常数时间的操作(执行时间固定的操作)

如果一个操作的执行时间不已样本本量为转移,每次都执行固定时间。

2,常见的常数操作

2.1 :加减乘除等,取余(+,-,*,/,%)

2.2 :常见的位运算(<<(带符号正或负进行计算),<<<(不带符号正或负进行计算),|,&,^)

2.3  :赋值,比较,自增,自减,单语句的if,else

2.4 : 数组寻址操作(link,list不是)

3,举例计算空间复杂度(选择排序)

在列表中,从下标0到n-1开始寻找最小值,放在0位置上。在从下标1到n-1开始寻找最小值(看一遍,比一比,还位置),放在1上,反复循环操作。

把整个流程拆分为基本常熟操作(如下)

常熟操作:an**2+bn+n+c

选择排序

第一次    n*(2(看+比)+1 (n个数,+1是换操作   二个数看1次, 比一次)

第二次    n-1*(看+比)+1 (n个数,+1是换操作)
第三次    n-2*(看+比)+1 (n个数,+1是换操作)
反复a次

 

所以选择排序复杂度为O(n^2)

4:意义

当处理大量数据时,我们会发现低价项是什么不重要,每一项系数是什么不是最重要的,最重要是是最高价项,

它是衡量流程复杂程度的一种指标,只与数据量有关,与过程之外的优化无关

5:常见的时间复杂度排序(好到差)

O(1)>O(logn)>O(N)>O(N*logN)>O(N*K) "例子:O(N*2)">O(k^N)"例子:O(2*N)">O(N!)

2,额外空间复杂度(记为O(n)流程决定)

2.1:作为输入的参数空间,不算额外空间,作为输出结果的空间,不算额外空间,必要的的,和实现目的有关的都不算。

2.1:当执行算法中,不需要额外空间,只需要额外几个变量,就可以完成算法,额外空间复杂度记为 O(1)“常数操作”

2.2:当执行算法中,与功能无关,自己需要开辟额外数组,就可以完成算法,额外空间复杂度记为 O(n)

3,常数项时间(实现代码时细节决定)

3。1:当时间复杂度与额外空间复杂度一样的情况下,判断哪一个更好算法的标准

3.2  :通常用代码直接进行测试判断,哪一个执行的更快,哪一个好

4,一个问题的最优解是什么意思?

一般情况下,在时间复杂度的指标上,一定要尽可能的低,先满足时间复杂度在使用最少的空间复杂度的算法流程。(特殊情况下,卡常熟项时间)

对数器

1,实现·是对数器?

1.1:你想要测的方法A

1.2:实现复杂度不好,但是对的方法B

1.3:实现一个随机样本产生器

1.4.:把A和B跑起来进行比较,看看结果是否一样

1.5:如果结果不一致,人工干涉用断点查看不同,改进方法A

1.6:当样本数量多时依然正确,则方法A就正确了

2,设置随机样本产生器

'''
    设计一个随机数组
    作者:ls富
'''
import random
def random_sum():
    i = 0
    ls = []
    size=int(random.random()*100)
    #设置列表个数
    while i < size :
        #随机增加元素(一个减一个)
        ls.append(int(random.random()*100-random.random()*100))
        i+=1
    return ls

if __name__ == '__main__':
   print(random_sum())

异或运算

1:与(&),按位与运算符:参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0

2:或(|),按位或运算符:只要对应的两个二进位有一个为1时,结果位就为1

3:异或(^),按位异或运算符:当两对应的二进位相异时,结果为1

4:取反(~),按位取反运算符:对数据的每个二进制位取反,即把1变为0,把0变为1

5:左位移(<<),运算数的各二进位全部左移若干位,由<<右边的数字指定了移动的位数,高位丢弃,低位补0 (通常写法:n*2+1<=>((n<<2)|1)

6:右位移(>>),把‘>>’左边的运算数的各二进制位全部右移若干位,>>右边的数字指定了移动的位数