chili coding 自留地

《算法导论》1 - 8


# 1 基础部分

    1 算法

        - 定义:算法,就是一个计算步骤的序列,功能是把输入转换成输出的

        - 应用:排序、数据库、互联网搜索、密码学、资源优化分配、地图寻路

        - 界限:NP 完全问题,是否存在有效算法是未知的

        - 并行:多线程下的算法



    2 插入排序

        - 增量方法

        - 排序子数组 A[0:i-1] 后,插入单个元素 A[i],产生排序好的 A[0:i]



    3 函数的增长

        - 大 O 记法,渐进上界

        - 大 𝛀 记法,渐进下界



    4 分治策略

        - 分治法

            - 分解

            - 解决

            - 合并

        - 应用

            - 排序

            - 最大子数组

            - nxn 矩阵乘法

        - 最大子数组

            - 求数字数组中,元素求和最大的子数组

            - 求解:

                - 找到中点 mid,则最大自数组和只会出现在下面 3 个情况

                - 1,完全位于 [low:mid],可递归

                - 2,完全位于 [mid:high],可递归

                - 3,位于 [i:mid:j],好求解

        - nxn 矩阵乘法

            - 拆成小矩阵相乘



    5 概率分析和随机算法

        - 有些情况下,仅仅改变程序本身并不能获得期望的输出

        - 比如,有时候需要将输入参数随机化,以避免输入值对结果的重大影响

        - 雇佣代理案例

        - 另外 4 个例子

            - 生日悖论:人数,两人生日相同概率超过1/2

            - 球与箱子:投球过程各种问题 ...

            - 抛硬币:最长连续正面的序列的期望长度

            - 雇佣问题变形



# 2 排序和顺序统计量

    6 堆排序

        - 堆概念

        - 维护堆的性质

        - 建堆

        - 堆排序算法

            - 建堆

            - 从底往上维护堆的性质(从半中间往即可)

            - 替换堆顶、末尾

            - 维护堆堆性质(堆顶)

            - 替换

            - ...循环

        - 堆的应用:优先列队

            - insert / maximum / extract-max / increase-key



    7 快速排序(原址重排...)

        - 选一个数字 x(比如最后一个)

        - 遍历数组中其他数字,

            - 大于 x,放 x 右边

            - 小于 x,放 x 左边

        - 对于左边的数组重复上述操作

            def quick_sort(arr):
                def _partition(arr, start, end):
                    x = arr[end]
                    index = start - 1
                    for j in range(start, end, 1):
                        if arr[j] <= x:
                            index += 1
                            arr[index], arr[j] = arr[j], arr[index]
                    index += 1
                    arr[index], arr[end], = arr[end], arr[index]


                    return index


                def _sort(arr, start, end):
                    if start < end:
                        q = _partition(arr, start, end)
                        _sort(arr, start, q - 1)
                        _sort(arr, q + 1, end)


                _sort(arr, 0, len(arr) - 1)



    8 线性时间排序

        - 决策树模型(需要对比)

        - 计数排序(感觉像是桶排序啊。。。)

            def counting_sort(input, output):
                times = [0] * (max(*input) + 1)
                for i in input:
                    times[i] += 1
                for i, t in enumerate(times):
                    while t > 0:
                        output.append(i)
                        t -= 1

        - 基数排序

            (举例子)纸带上三位数字排序,按位上单个数字排几次(从低位往高位)

        - 桶排序

            bucket_sort

            与计数排序有些类似,处理的是均匀分布的输入


reply ( 0 )