• 周二. 3月 5th, 2024

    数据结构笔记(2) 算法

    root

    3月 20, 2021 #数据结构

    1. 算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
    2. 算法有5个基本我: 输入、输出、有穷性、确定性和可行性。
    3. 算法设计的要求:1)正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
    2) 可读性: 算法设计的另一目的是为了便于阅读、理解和交流。
    3)健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。

    4. 算法效率的度量方法1)事后统计方法这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低。
    2)事前分析估算方法在计算机程序编制前,依据统计方法对算法进行估算。
    5. 函数的渐近增长
    函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n).

    如: 算法A(2n+3)和算法B(3n+1)当n=2时 算法A和算法B相等, 从表可以看出n>N(N即是整数2) 所有算法B>算法A
    随着n的增大,后面的+3还是+1其实是不影响最终的算法变化的,例如算法A’与算法B’ , 所以我们可以忽略这些加法常数。

    当n<=3的时候,算法C要差于算法D(因为算法C次数比较多),但当n>3后,算法C的优势就越来越优于算法D了。算法C’的次数随着n的增长,远小于算法D’ 。 说明 算法的渐近增长与最高次项相每次的常数并不重要。

    最高次项的指数大的,函数随着n的增长,结果也会变得增长特别快。
    判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略,而更应该关注最高阶项的阶数。

    root