打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
大数据算法(一)亚线性算法

正文

来源:大数据算法 王宏志 

一、概述

大数据定义:在给定的资源约束下,以大数据为输入,在给定时间约束内可以生成满足给定约束结果的算法。

大数据特点:4V

大数据算法可以不是:

  • 精确算法

  • 内存算法

  • 串行算法

  • 仅在电子计算机上运行的算法

大数据算法不仅是:

  • 云计算

  • MapReduce

  • 大数据分析和挖掘的算法

难度:

  • 访问全部数据时间过长

               读取部分数据 亚线性算法

  • 数据难以放入内存

               将数据存储到磁盘上 外存算法

               仅基于少量数据进行计算 空间亚线性算法

  • 单个计算机难以保存全部数据

               并行处理 并行算法

  • 计算机能力不足或知识不足

              人来帮忙 众包算法

大数据上问题求解计算问题的过程

大数据的算法设计技术

  • 精确算法设计方法

  • 并行计算

  • 近似计算

  • 随机算法

  • 在线算法/数据流算法

  • 外存算法

  • 面向新型体系结构的算法

  • 现代优化算法

大数据算法分析

  • 时间空间复杂性

  • IO复杂性

  • 结果质量(近似比、competitive ratio)

  • 通讯复杂性

二、亚线性算法概述

1.定义

时间/空间/IO/通讯/能量等消耗是o(输入规模)

亚线性时间算法

  • 性质检测算法

  • 亚线性时间近似算法

亚线性空间算法

  • 数据流算法

2.空间亚线性算法-水库抽样

输入:一组数据,其大小未知

输出:这组数据的k个均匀抽样

要求:

  • 仅扫描数据一次

  • 空间复杂性为O(k) 和抽样大小有关,和整个数据无关

  • 扫描到数据的前n个数字时(n>k),保存当前已扫描数据的k个均匀抽样

算法:

  • 申请一个长度为k的数组A保存抽样

  • 保存首先接收到的k个元素

  • 当接收到第i个新元素t时,以k/i的概率随机替换A中的元素(即生成[1, i]间随机数j,若k<=j,则以t替换A[j]

3.时间亚线性计算算法-平面图直径

输入:m个顶点的平面图,任意两点之间的距离存储在矩阵D中,即点i到点j的距离为Dij

  • 输入大小是n=m的平方

  • 最大的Dij是图的直径

  • 点之间的距离对称且满足三角不等式

输出:该图的直径和距离最大的Dij

要求:运行时间为o(n)

算法:

动机:无法在要求的时间内得到精确算法,寻找近似算法

近似算法

  • 任意选择k<=m

  • 选择使得Dkl最大的l

  • 输出Dkl和(k, l)

近似比

Dij <= Dik+Dkj <= Dkl+Dk l<= 2Dkl 因而近似比为2

近似时间

4.近似算法 

什么是近似算法

  • 近似算法主要用来解决优化问题

  • 能够给出一个优化问题的近似优化解的算法

近似算法解的近似度

  • 问题的每一个可能的解都具有一个代价

  • 问题的优化解可能具有最大或最小代价

  • 我们希望寻找问题的一个误差最小的近似优化解

我们需要分析近似解代价与优化解代价的差距

  • Ratio Bound

  • 相对误差

  • (1-ε)-近似

5.时间亚线性判定算法-全0数组判定

输入:包含n个元素的0,1数组A

输出:A中的元素是否全是0

要求:运行时间为o(n)

判定问题的近似:

  • 无法在要求的时间内得到精确解,寻找近似解

                判定问题如何近似

  • 输入满足某种性质或者远非满足此性质

 

  •  ε-远离

            对于输入x,如果x到L中的任意字符串的汉明距离至少为ε|x|,则x是ε-远离L的

全0数组判定问题的近似

  • 是否A=00...0或者其包含1的个数大于 εn?

算法描述:

  • 在A中随机独立抽取s= 2/ε个位置上的元素

  • 检查抽样,若不包含1,则输出“是”,若包含1,则输出“否”

判定精确性分析

  • 如果A是全0数组,始终输出“是”

  • 如果A是 ε-远离的,

运行时间:O(s)

证据引理:

  • 如果一次测试以大于等于p的概率获得一个证据,那么s=2/p轮测试得到证据的概率大于等于2/3

判定算法的定义

三、亚线性算法案例

本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
【热】打开小程序,算一算2024你的财运
搜索算法具体分类总结
信息学竞赛→图片作品→查看图片→线性表的数组实现
最短路径算法汇总
打破机器学习中的小数据集诅咒
给大家推荐两本自学贝叶斯推理的入门书籍
数据结构知识:链表,队列和栈的区别
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服