应用介绍

此文档是python相关技术。

import os,sys 
parentdir = os.path.dirname(os.path.dirname(os.path.abspath(__file__))) 
sys.path.insert(0,parentdir) 

import xmind
from xmind.core.markerref import MarkerId
xmind_name="algorithm"
w = xmind.load(os.path.dirname(os.path.abspath(__file__))+"\\"+xmind_name+".xmind") 
s2=w.createSheet()
s2.setTitle("algorithm")
r2=s2.getRootTopic()
r2.setTitle("算法")


content={
'1.数据结构':[
    {'链表':[
        '指针',
        '循环链表',
        '双向链表',
        '查找时间复杂度O(n)',
        '添加或删除时间复杂度O(1)'
    ]},
    {'数组':[
        '连续空间',
        '查找时间复杂度O(1)',
        '添加或删除时间复杂度O(n)'
    ]},
    {'栈':[
        '后进先出',
        '入栈，出栈'
    ]},
    {'队列':[
        '入队，出队',
        '先进先出'
    ]},
    {'哈希表':[
        '键（key）和值（value）',
        '哈希值取余后冲突：链表解决'
    ]},
    {'堆':[
        '树',
        '优先队列',
        '子结点>父结点',
        '取最小值的时间复杂度:O（1）',
        '数据量n，树高log2n',
        '取数据O（logn）:将最后的数据移到顶端，然后一边比较它与子结点数据的大小，一边往下移动',
        '添加数据O（logn）:运行时间与树的高度成正比'
    ]},
    {'二叉查找树':[
        '结点值>其左子树上任意一个结点的值',
        '结点值<其右子树上任意一个结点的值',
        '最小结点:从顶端开始，往其左下的末端寻找',
        '最大结点:从顶端开始，往其右下的末端寻找',
        '二分查找算法思想的树形结构',
        '比较大小和移动的次数最多log2n->时间复杂度为O（logn）',
        '如树的形状朝单侧纵向延伸，时间复杂度为O（n）',
        '平衡二叉查找树:数据结构可以修正形状不均衡的树，让其始终保持均衡形态，以提高查找效率',
        'B树:子结点数扩展为m,形状均衡的树'
    ]}],
'2.排序':[
    {'冒泡排序':[
        '从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置',
        '总的比较次数为（n-1）+（n-2）+…+1≈n2/2',
        '时间复杂度为O（n2）'
    ]},
    {'选择排序':[
        '从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换',
        '总的比较次数为（n-1）+（n-2）+…+1≈n2/2',
        '复杂度为O（n2）'
    ]},
    {'插入排序':[
        '从右侧的未排序区域内取出一个数据，然后将它插入到左侧已排序区域内合适的位置上'
        '时间复杂度为O（n2）'
    ]},
    {'堆排序':[
        '按降序来构建堆,并从最大的数据开始取，将取出的数据反序输出',
        'n个数据存进堆里:O（nlogn）',
        '每轮取出最大的数据并重构堆:O（logn）',
        '共有n轮,整体看堆排序的时间复杂度为O（nlogn）'
    ]},
    {'归并排序':[
        '把序列分成长度相同的两个子序列，无法继续往下分时，对子序列进行归并',
        '归并:需重复比较首位数据大小->移动较小的数据,把两个排好序的子序列合并成一个有序序列',
        '归并:花费时间为子序列的总长度，每行O（n）',
        '总行数：log2n行，时间复杂度为O（nlogn）'
    ]},
    {'快速排序':[
        '在序列中随机选择一个基准值，将除基准值以外的数分为“比基准值小的数”和“比基准值大的数”',
        '每行中每个数字都需要和基准值比较大小，每行O（n）',
        '总的时间复杂度为O（nlogn）'
    ]}
],
'3.数组的查找':[
    '线性查找',
    '二分查找：数组有序'
],
'4.图的搜索':[
    '顶点+边',
    '加权图：边的权重',
    '有向图',
    {'广度优先搜索':[
        '从起点开始，由近及远进行搜索,目标顶点离起点越近，搜索结束越快',
        '候补顶点用“先入先出”（FIFO）方式管理，使用“队列”的数据结构'
    ]},
    {'深度优先搜索':[
        '沿着一条路径不断往下，进行深度搜索',
        '候补顶点用“后入先出”（LIFO）方式管理，使用“栈”的数据结构'
    ]},
    {'区别':[
        '选择哪一个候补顶点作为下一个顶点的基准不同',
        '广度优先搜索选择最早成为候补的顶点',
        '深度优先搜索选择最新成为候补的顶点'
    ]},
    {'贝尔曼-福特算法':[
        '在图中求解最短路径问题的算法',
        '图顶点数设为n、边数设为m，算法经过n轮更新后停止，每轮更新中需对各个边进行1次确认，1轮花费的时间是O（m）',
        '整体时间复杂度O（nm）',
        '一个闭环中边的权重总和是负数，不存在最短路径',
        {'过程':[
            '设置起点为0，其他顶点为无穷大（∞）',
            '计算边从一端到另一端的权重,方法=顶点原本的权重+边的权重',
            '对所有的边进行更新操作',
            '重复对所有边的更新操作，直到权重不能被更新为止'
        ]}
    ]},
    {'狄克斯特拉算法':[
        '图顶点数设为n、边数设为m，算法的时间复杂度是O（n2）,对数据结构进行优化，时间复杂度O（m+nlogn）',
        '如果闭环中有负数权重，会算出一个错误的最短路径出来',
        {'过程':[
            '设置起点为0，其他顶点为无穷大（∞）',
            '候补顶点:目前所在的顶点直达且尚未被搜索过的顶点',
            '计算候补顶点的权重,如果计算结果小于候补顶点的值，更新',
            '从候补顶点中选出权重最小的顶点作为新顶点，重复上述操作'
        ]}
    ]},
    '不存在负数权重时，使用效率较高的狄克斯特拉算法',
    '存在负数权重时，使用可以得到正确答案的贝尔曼-福特算法'
],
'5.安全算法':[
    {'数据传输的四个主要问题':[
        '窃听————加密',
        '假冒————消息认证码/数字签名',
        '篡改————消息认证码/数字签名',
        '事后否认————数字签名'
    ]},
    {'哈希函数':[
        {'特征':[
            '1.输出的哈希值数据长度不变',
            '2.输入数据相同，输出哈希值也相同',
            '3.输入相似的数据并不会导致输出的哈希值也相似',
            '4.哈希冲突',
            '5.不可逆：不能从哈希值反向推算出原本的数据',
            '6.求哈希值的计算容易'
        ]},
        '算法代表：MD5、SHA-1和SHA-2',
        'SHA-2应用广泛，MD5和SHA-1存在安全隐患，不推荐使用',
    ]},
    {'加密':[
        {'共享密钥加密':[
            '对称加密：加密和解密使用相同密钥',
            '算法：凯撒密码、AES（应用广泛）、DES、动态口令',
            {'问题':[
                '密钥分配问题————使用“密钥交换协议”和“公开密钥加密”两种方法',
                '密钥需求数量随着发送人增多而增多'
            ]} 
        ]},
        {'公开密钥加密':[
            '非对称加密：加密和解密使用不同密钥',
            '加密用的：公开密钥',
            '解密用的:私有密钥',
            '算法：RAS算法（应用广泛）、椭圆曲线加密算法等',
            {'过程':[
                '1.接收方B生成公开密钥和私有密钥',
                '2.把公开密钥发送给A',
                '3.A使用B发来的公开密钥加密数据',
                '4.A将密文发送给B, B用私有密钥对密文进行解密'
            ]},
            {'问题':[
                '中间人攻击(通过中途替换公开密钥来窃听数据)：使用数字证书',
                '耗时：使用混合加密'
            ]}
        ]},
        {'混合加密':[
           {'过程':[
                '1.A将密钥通过共享密钥加密后，发送给B【共享密钥】',
                '2.B事先生成公开密钥和私有密钥',
                '3.B将公开密钥发送给A【公开密钥】',
                '4.A使用收到的公开密钥，对共享密钥加密中需要使用的密钥进行加密【新的共享密钥】',
                '5.A将加密后的密钥发送给B【新的共享密钥】',
                '6.B使用私有密钥对密钥进行解密',
                '8.A将使用新的共享密钥加密好的数据发送给B',
                '加密数据时使用的是处理速度较快的共享密钥加密'
            ]},
            '为网络提供通信安全的SSL协议也应用了混合加密方法'
        ]},
        {'迪菲-赫尔曼密钥交换':[
            '通过将双方共有的秘密数值隐藏在公开数值相关的运算中，实现双方密钥的安全交换',
            {'过程':[
                '1.A把密钥P发送给B',
                '2.A和B各自准备自己的私有密钥SA和SB',
                '3.A利用密钥P和私有密钥SA合成新的密钥P-SA',
                '4.B也利用密钥P和私有密钥SB合成新的密钥P-SB',
                '5.A将密钥P-SA发送给B, B也将密钥P-SB发送给A',
                '6.A将私有密钥SA和收到的密钥P-SB合成为新的密钥SA-P-SB',
                '8.B也将私有密钥SB和收到的密钥P-SA合成为新的密钥P-SA-SB',
                '9.A和B都得到了密钥P-SA-SB,此密钥将作为“加密和解密密钥”'
            ]}
        ]}
    ]},
    {'消息认证码':[
        '由密钥和密文生成的值，简称MAC',
        {'功能':[
            '认证',
            '检测篡改'
        ]},
        {'问题':[
            '生成一方和检测一方持有相同密钥，不能确定MAC由哪方生成'
        ]}
    ]},
    {'数字签名':[
        '使用公开密钥加密生成',
        '将“只能由A来加密的密文”作为“签名”使用',
        {'功能':[
            '认证',
            '检测篡改',
            '预防事后否认问题的发生'
        ]},
        {'问题':[
            '无法保证公开密钥来自信息发送者'
        ]}
    ]},
    {'数字证书':[
        '保证公开密钥的正确性',
        {'过程':[
            '1.A需向认证中心CA申请发行证书，证明公开密钥PA确实由A生成',
            '2.认证中心里保管着其自己的公开密钥PC和私有密钥SC',
            '3.A将公开密钥PA和包含邮箱信息的个人资料发送给认证中心',
            '4.认证中心对收到的资料进行确认，判断其是否为A本人的资料',
            '确认完毕，认证中心使用自己的私有密钥SC，根据A的资料生成数字签名',
            '5.认证中心将生成的数字签名和资料放进同一个文件中,把这个文件发送给A,此文件即A的数字证书',
            '6.A将作为公开密钥的数字证书发送给了B',
            '8.B收到数字证书后，确认证书里的邮件地址确实是A。接着，获取了认证中心的公开密钥',
            '9.B对证书内的签名进行验证，判断是否为认证中心给出的签名',
            '证书中的签名只能用认证中心的公开密钥PC进行验证,如验证结果无异常，说明这份证书的确由认证中心发行',
            '10.确认了证书是由认证中心发行的，且邮件地址是A的后，B从证书中取出A的公开密钥PA',
            '如此，公开密钥从A传到了B'
        ]},
        '个人的证书会与他的邮箱信息相对应',
        '服务器证书与域名信息相对应',
        '数字证书：通过认证中心来担保公开密钥的制作者，这一系列技术规范被统称为“公钥基础设施“'
    ]}],
'6.聚类':[
    '定义数据间的差距,将相似的对象分为一组',
    {'k-means算法':[
        '准备好需要聚类的数据，决定簇的数量',
        '随机选择n个点作为簇的中心点',
        '将数据分到相应的簇中',
        '将中心点移到重心的位置'
        '重复执行上面两个操作，直到中心点不再发生变化'
    ]}],
'7.其他算法':[
    {'欧几里得算法':[
        '计算两个数的最大公约数:重复做除法'
    ]},
    {'素性测试':[
        '根据费马小定理判断一个数是否为素数'
    ]},
    '网页排名',
    '汉诺塔'
]
}

#构建xmind
xmind.build(content,r2)
#保存xmind
xmind.save(w,os.path.dirname(os.path.abspath(__file__))+"\\"+xmind_name+".xmind")