Mark'sBLOG
CARD
jinyaoMa
issue, func, flow, std, solve
16 | 9 | 25
SKIN
SETTINGS
Night Shift
Disable Canvas
简体中文
中文
|
English
|
日本語
PAGE CONTENT
算法之基础
2020-04-18
2020-04-19
1.5k
11 min.

算法基础,了解算法的基础知识,算法的种类,知道什么是好算法。

# 算法特性

  • 输入:可以有零个或多个参数
  • 输出:必须有一个或多个结果
  • 有穷性:算法必须会结束,没有无限循环
  • 确定性:有唯一结果
  • 可行性:算法每一步都能通过执行有限次数完成

# 算法设计要求

  • 正确性:算法至少具有输入、输出和过程明确的加工处理,正确反映问题的需求,最后得到期望的答案
    • 算法程序没有语法错误
    • 算法程序对于合法输入能产生期望的答案
    • 算法程序对于非法输入能产生警告和提示
    • 算法程序对于故意掉难得测试输入都能产生期望的结果
  • 可读性:算法便于阅读、理解和交流
  • 健壮性:能够处理异常、崩溃或莫名其妙的结果
  • 高时间效率和低存储量:算法要考虑处理速度和内存用量

# 算法效率度量方法

  • 事后统计方法:通过执行多个输入测试,记录执行时间平均值
  • 事前估算方法:通过统计方法对算法进行估算,涉及以下因素
    1. 算法策略,例子使用公式或者循环等
    2. 编译后的代码质量,基础操作的次数统计
    3. 问题的输入规模,例子数值大小或元素数量等
    4. 机器执行指令的速度,硬件性能

算法基础种类分别有: 1nn*n

一般使用公式或瀑布式条件判断的算法策略属于 1 ;使用单个循环的属于 n ;使用嵌套循环的属于 n*n 。3 种算法中往往常数算法 1 要优于 nn*n 。给以下基础操作次数公式分类:

  • 1359
  • nnn+12n+3
  • n*nn^2n^2+52n^3+1

一般判断算法好坏,更应该关注函数公式的主项:指数最高项。 比如算法 2n^2+n+3 对比算法 n^3+2n+1 ,因为 2n^2 指数低于 n^3 ,所以算法 2n^2+n+3 优于算法 n^3+2n+1

# 怎么分析一个算法的输入时间?

  • 抽象算法:去除算法中循环的外包装、条件的判断、变量的声明、打印输出等操作
  • 指令计数:统计关联的输入模式下基础操作的数量

# 求和 1-100 的算法例子分析

以下算法一,算法策略使用 循环 ,编译后的代码质量为 n 次,问题的输入规模 100 ,机器执行指令的速度取决于算法运行所在计算机。

let sum = 0, i = 1, n = 100;
for (; i <= n; i++) {
  sum += i;                  // 执行 n 次
}

以下算法二,算法策略使用 公式 ,编译后的代码质量为 1 次,问题的输入规模 100 ,机器执行指令的速度取决于算法运行所在计算机。

let sum = 0, i = 1, n = 100;
sum = (i + n) * n  / 2;      // 执行 1 次

对比以上算法,它们的输入规模都是 100 ,在同一计算机运行的情况下,算法一的基础操作次数受输入规模的影响,造成工作量超出算法二所以算法二效率更高

# 求和 3x3 表格内数值的例子分析

以下表格遍历例子,算法策略使用 嵌套的循环 ,编译后的代码质量为 n^2 次,问题的输入规模 3x3 ,机器执行指令的速度取决于算法运行所在计算机。

let sum = 0, 
    table = [
      [1, 2, 3],
      [4, 5, 6],
      [7, 8, 9],
    ];
for (let i = 0; i <= table.length; i++) {
  for (let j = 0; j <= table[i].length; j++) {
    sum += table[i][j];      // 执行 n^2 次
  }
}

以上算法,它根据表格的大小,基础操作的数量是以指数上升的,所以 3x3 的表格内数值总和计算一共有基础操作 3^2 等于 9 次

# 用大 O 记法表示算法时间复杂度

复杂度分为:时间复杂度空间复杂度 一般计算 “复杂度” 是指 “时间复杂度”,而不是空间复杂度,目前主流还是时间复杂度,不求用内存换取时间。

T(n) = O(f(n))f(n) 为算法的函数或入口,随着输入规模 n 的增长, T(n) 增长最慢的算法为最优算法。因为以下原因:

基础操作数量 = 时间

所以当 n 翻倍时,基础操作数量增长越少,花费的时间越少。

上面用到的三个求和算法例子,如果用大 O 表示算法的时间复杂度分别为 O(1)O(n)O(n^2)

大 O 记法表示时间的增长率

  • O(1) :增长率不变
  • O(n) :增长率倍数增长
  • O(n^2) :增长率指数增长

# 推导大 O 阶方法

用一下方法来推导 52n+3n(n+1)/2O(logn) 的大 O 阶:

  1. 用常数 1 取代所有加法常数
  2. 只保留最高阶项
  3. 最高阶项不是 1 的话,去除这个项相乘的常数

5 => O(1)2n+3 => O(n)n(n+1)/2 => O(n^2)

一面这个例子的话就是 O(logn)

let i = 1, n = 100;
while (i < n) {
  i *= 2; // 2^x = n,那么 x = log(2)n,x为循环次数
}

# 常见的时间复杂度

例子 时间复杂度 术语
5 O(1) 常数阶
3n+4 O(n) 线性阶
3n^2+4n+5 O(n^2) 平方阶
3log(2)n+4 O(logn) 对数阶
2n+3nlog(2)n+14 O(nlogn) nlogn 阶
n^3+2n^2+4n+6 O(n^3) 立方阶
2^n O(2^n) 指数阶

时间复杂度对比: O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

本文参考: 【C 语言描述】《数据结构和算法》(小甲鱼)(opens new window)

The post above ended Thanks for your reading
Come on! Write some comments, and your suggestions will improve the quality of my creative!
FRIEND ME
QQ
WeChat
Post Author: jinyaoMa
Post Link: /
Copyright Notice: All articles/posts in this website are licensed under BY-NC-SA unless stating additionally.
Enable Read Mode
COMMENTS
DEFAULT