• 周五. 3月 1st, 2024

    数据结构笔记2.算法

    1、算法的定义

    算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

    2. 算法的特性

    算法具有五个基本特性: 输入、输出、有穷性、确定性和可行性。

    3. 算法的设计要求

    正确性:算法至少应该具有输入,输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。

    可读性:算法设计的另一目的是为了便于阅读、理解和交流

    健壮性:当输入不合法数据时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。

    4. 函数的渐近增长

    给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比 g(n)大,那么,我们说f(n)的增长渐近快于g(n) .

    5. 算法的时间复杂度

    在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级.

    算法时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n)).它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度.其中f(n)是问题规模n的某个函数.

    这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法.

    一般情况下,随着n的增大,T(n)增长慢的算法为最优算法.

    O(1)常数阶

    O(n)线性阶

    O(n^2)平方阶

    6. 推导大O阶方法

    1. 用常数1取代运行时间中的所有加法常数
    2. 在修改后的运行次数函数中,只保留最高阶项.
    3. 如果最高阶项存在且不是1,则去除与这个项相乘的常数.
    4. 得到结果就是大O阶.

    7. 常数阶O(1)

    int sum=0, n=100;  /*执行一次*/
    sum = (1+n)*n/2; /*执行一次*/
    printf("%d",sum); /*执行一次*/

    这个算法的运行次数函数是f(n)=3, 根据我们推导大O阶的方法
    第一是把常数阶3改为1.
    在保留最高阶项时发现,它根本没有最高阶,所以这个算法的时间复杂度为O(1)

    8. 线性阶O(n)

    int i;
    for (i=0;i<n;i++) 
    {
     /*时间复杂度为O(1)的程序步骤序列*/
    }

    这个算法循环体中的代码需要执行n次. 它没有常数阶,最高阶项常数为1, 故它的时间复杂度为O(n).

    9. 对数阶O(logN)

    int count = 1;
    while (count<n)
    {
         count = count * 2;
         .....
    }

    由于每次count乘以2之后,就距离n更近一分.也就是说有多少个2相乘后大于n,则会退出循环.由2^x=n得 x=log以2为底N的对数.所以这个循环的时间复杂度为O(logN).

    10. 平方阶O(n^2)

    int i,j
    for(i=0; i<n; i++) {
      for(j=0; j<n; j++) {
          ...
      }
    }

    这里有两层循环, 一层循环的时间复杂度为O(n) , 双层循环的时间复杂度为O(n^2), 两层循环次数的不一致最后推导出一个常数项乘以一个数的平方. 常数项根据大O推导法省略. 最后为O(n^2).

    11. 常见的时间复杂度

    常用的时间复杂度所耗费的时间从小到大

    算法的最坏情况运行时间是一种保证,在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏的情况的运行时间。

    12. 算法的空间复杂度

    算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n) = O(f(n)), 其中,n为问题的规模,f(n)为语句关于n所占存储窠的函数。

    root