程序员经验分享-hwhale

k-means 的时间复杂度是多少？

2024-02-03

我正在经历k-means 维基百科页面 http://en.wikipedia.org/wiki/K-means_clustering。根据算法，我认为复杂度是O(n*k*i) (n= 总元素，k= 簇迭代次数）

那么有人可以向我解释一下维基百科上的这个说法以及这个 NP 有多难吗？

If k and d (the dimension) are fixed, the problem can be exactly solved in time O(ndk+1 log n), where n is the number of entities to be clustered.


这取决于你叫什么k-means.

寻找全局最优值的问题k-means https://en.wikipedia.org/wiki/K-means_clustering目标函数

is NP-hard, where Si is the cluster i (and there are k clusters), xj is the d-dimensional point in cluster Si and μi is the centroid (average of the points) of cluster Si.

但运行固定次数t的迭代次数标准算法 https://en.wikipedia.org/wiki/Lloyd%27s_algorithm只需要O(t*k*n*d), for n (d-维）点，其中k是质心（或簇）的数量。这就是实际实现所做的（通常在迭代之间随机重新启动）。

标准算法仅逼近上述函数的局部最优，所有的算法也是如此k- 表示我见过的算法。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

timecomplexity

kmeans

k-means 的时间复杂度是多少？ 的相关文章

  • 如何计算两个ip之间的主机数量？ C＃

    我有两个ip 1 1 1 1 1 2 4 4 4 4 显然这只是一个例子 这是一个动态计算器 如果子网掩码不相关 我如何计算所述 ip 之间的主机数量 要计算 理论 IP 地址的数量 您需要将每个 IP 地址转换为其 32 位整数格式 这实

  • 合并字符数组中的最小重复次数

    假设我有两个数组 我想合并它们 以便合并后的数组具有最小重复次数 例如 x x 是重复 arr1 x d d m f m arr2 d d x f f m 唯一的条件是在合并数组中 元素来自arr1 and arr2必须出现在各自的订单中a

  • 反转二进制网络

    如何反转二元方程 以便找到哪些输入将产生给定的输出 Example Inputs i0 through i8 Outputs o0 through o8 Operators XOR AND 二元方程 1 i0 1 i1 0 i2 1 i3

  • 用 Java 创建迷宫求解算法

    我被分配了用 Java 创建迷宫求解器的任务 这是任务 Write an application that finds a path through a maze The maze should be read from a file A

  • Scikit Learn - K-Means - 肘部 - 标准

    今天我想学习一些关于 K means 的知识 我已经了解该算法并且知道它是如何工作的 现在我正在寻找正确的 k 我发现肘部准则作为检测正确的 k 的方法 但我不明白如何将它与 scikit learn 一起使用 在 scikit learn

  • 使到 n 个点的集合的欧氏距离之和最小的点

    我有一组点W x1 y1 x2 y2 xn yn 在 2D 平面上 你能找到一种算法 将这些点作为输入并返回一个点 x y 在 2D 平面上 距以下点的距离之和最小W 换句话说 如果 di Euclidean distance x y xi

  • 32 位数字中 1 的数量

    我正在寻找一种在 32 位数字中包含 1 数量的方法 之间不使用循环 任何人都可以帮助我并向我提供代码或算法吗 这样做 提前致谢 See Integer bitCount int http java sun com javase 6 doc

  • 如何查找给定字符串中仅出现一次的第一个字符[关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi

  • 编程 Pearls - 随机选择算法

    Programming Pearls 第一版第 120 页介绍了从 N 个整数总体中选择 M 个等概率随机元素的算法 InitToEmpty Size 0 While Size lt M do T RandInt 1 N if not Me

  • 将嵌套字典中的所有键从camelCase转换为snake_case

    我有一本类似这样的字典 firstName abc lastName xyz favoriteMovies Star Wars The lone ranger favoriteCountries country China capitalC

  • 如何高效地在屏幕上精确绘制N个点？

    这听起来是一个简单的问题 但我发现要获得良好的性能是非常棘手的 我提出的第一个算法是随机绘制点 从一组中检查是否已绘制 否则绘制 如果我们只绘制几个点 那么这种方法效果很好 但当我们接近填满屏幕时 速度会灾难性地减慢 我想出的最好的方法是构

  • 通过分布式数据库聚合作业优化网络带宽

    我有一个分布式 联合数据库 结构如下 数据库分布在三个地理位置 节点 每个节点集群有多个数据库 关系数据库是 PostgreSQL MySQL Oracle 和 MS SQL Server 的混合体 非关系数据库是 MongoDB 或 Ca

  • 我需要一个支持高效随机访问和 O(k) 插入和删除的容器

    我再次尝试问同样的问题question https stackoverflow com questions 3808708 delete parts of a dynamic array and grow other 但我最终提出了一个不同

  • 使用 scikit 包在 Python 中绘制集群区域的边界

    这是我处理 3 个属性 x y 值 中的数据聚类的简单示例 每个样本代表其位置 x y 及其所属变量 我的代码发布在这里 x np arange 100 200 1 y np arange 100 200 1 value np random

  • 最慢的计算复杂度（Big-O）

    在这些算法中 我知道 Alg1 是最快的 因为它是 n 平方的 接下来是 Alg4 因为它是 n 的立方 然后 Alg2 可能是最慢的 因为它是 2 n 这应该具有非常差的性能 然而Alg3和Alg5在我的阅读速度方面还没有遇到过 这两种算

  • 由周期表元素形成的最大单词的算法

    我想为以下问题场景编写一个算法 根据元素周期表元素的名称 找到可以组成的最大单词 符号如Na Ne等应被视为单个元素 这是在一家知名公司的求职面试中被问到的 有人可以帮我解决这个问题吗 我认为更好的方法是检查字典中的每个单词 看看是否可以从

  • 时间复杂度和运行时间有什么区别？

    时间复杂度和运行时间有什么区别 它们是一样的吗 运行时间是指程序运行所需的时间 时间复杂度是对输入大小趋于无穷大时运行时间渐进行为的描述 您可以说运行时间 是 O n 2 或其他什么 因为这是描述复杂性类和大 O 表示法的惯用方式 事实上

  • Karasuba算法递归过多

    我正在尝试用 c 实现 Karasuba 乘法算法 但现在我只是想让它在 python 中工作 这是我的代码 def mult x y b m if max x y lt b return x y bm pow b m x0 x bm x1

  • 无需构建树即可预测霍夫曼压缩比

    我有一个二进制文件 我知道其中每个符号出现的次数 如果我要使用霍夫曼算法压缩它 我需要预测压缩文件的长度 我只对假设的输出长度感兴趣 而不对单个符号的代码感兴趣 因此构建霍夫曼树似乎是多余的 作为一个例子 我需要得到类似的东西 包含 4 个

  • 数组中连续元素的最大乘积

    我在现场面试的时候被问到了这个算法问题 由于没有要求我签署保密协议 我将其发布在这里寻求答案 给定一个数组REAL不包含 0 的数字 找到产生最大乘积的连续元素 该算法应在线性时间内运行 我考虑过以下方法 使用两个数组 第一个是利用DP思想

随机推荐

  • 如何使用 std 向量初始化 std 堆栈？

    我需要放一个std vector进入一个std stack 到目前为止 这是我的方法 我正在构建纸牌游戏 void CardStack initializeCardStack std vector

  • 在 Fluent NHibernate 中使用公式引用实体

    我有一个架构N 1父子关系存储在另一个表中并通过公式选择 是否可以使用公式将该实体映射到父实体 public class ParentEntity public virtual int ParentId get set public vir

  • 具有定义值的 Typescript 动态对象键

    我遇到一个问题 试图让打字稿为我识别 javascript 对象的键 同时强制每个键的值类型 因为我想创建对象键的类型 所以我不能只创建一个常规的type MyObject key string

  • Git 分支 - HEAD 分支上的拉取请求也需要之前的分支提交

    我来自 IBM RTC 所以我需要习惯 Git 我已经分叉了一个存储库 在我的主分支上完成了几次提交并打开了一个拉取请求 Pull request original repository master lt my repository ma

  • 如何在 C# 中将 Decimal 格式化为以编程方式控制的小数位数？

    如何将数字格式化为固定的小数位数 保留尾随零 其中位数由变量指定 e g int x 3 Console WriteLine Math Round 1 2345M x 1 234 good Console WriteLine Math Ro

  • Keras 嵌入层在函数式 API 中具有可变长度

    我有以下适用于可变长度输入的顺序模型 m Sequential m add Embedding len chars 4 name embedding m add Bidirectional LSTM 16 unit forget bias

  • 将运输与 Ruby on Rails 集成

    将运输报价添加到我的购物车的最佳方法是什么 我网站的基本流程是 1 User selects products 2 User is shown cart 3 repeat 1 and 2 until User wants to pay 4

  • PostgreSQL：SELECT DISTINCT ON 表达式必须与初始 ORDER BY 表达式匹配

    假设我有以下 PostgreSQL 表 名为products CREATE TABLE IF NOT EXISTS mytable id serial NOT NULL PRIMARY KEY label VARCHAR 50 NOT NU

  • 为什么我在二叉搜索树中找不到左和右？

    我遇到以下代码片段的问题 using System using System Collections Generic using System Text namespace trees by firas class Program stat

  • 使用$_REQUEST作为数据是错误的吗？

    所以 我已经编码了一点 2年 了 我有一个非常主观的问题 使用 REQUEST作为数据是错误的吗 顺便说一句 这主要与身份验证有关 如果您考虑数据出现的 3 种方式 REQUEST 它可以来自 cookie 表单或查询字符串 现在 我知道大

  • 远程链接中奇怪的下划线参数

    我使用 Rails3 JQuery 和 will paginate gem 来制作远程分页链接 已知的解决方案是 pagination a live click function getScript this href return fal

  • 无法加载文件 %CommonDir%\publish.tlb

    每次我安装并尝试启动 Microsoft Visual Studio 2012 时 都会收到以下弹出窗口 其中包含以下消息 无法加载文件 CommonDir publish tlb 由于找不到该文件 尝试修复此情况失败 请重新安装该程序 我

  • 儒略日期到常规日期的转换

    如何使用 java API 将代表 2013 年 11 月 18 日的儒略日期 2456606 转换为字符串格式 18 11 2013 我尝试执行下面的代码 但它没有给我正确的答案 欢迎对以下代码进行任何更正 String j 245660

  • opencv VideoCapture 在线程中被阻塞

    我需要一些有关在另一个线程中使用 opencv VideoCapture 的帮助 当我使用视频截取 http docs opencv org modules highgui doc reading and writing images an

  • 二维码怎么能存储这么多数据呢？

    快速谷歌搜索结果显示 QR 码可以容纳近 3kb 8 位 数据 但这不就是用黑 白点来表示位吗 如果是这样的话 代码上不可能有超过 20 000 个点 所以我显然是误解了 有人可以解释它是如何工作的吗 电装波says http www de

  • 接受 Rails 使用条款

    在 Rails 应用程序中添加接受使用条款的检查的最佳方法是什么 我似乎无法得到validates acceptance of工作得很好 我在我的用户模型中添加了一个布尔值 有必要吗 然后有一个返回 true false 的复选框 我觉得我

  • AS3 中的 URL 编码变量？

    尝试通过传递变量时出现以下错误URLRequestMethod POST 错误 错误 2101 传递给 URLVariables decode 的字符串必须是包含名称 值对的 URL 编码查询字符串 有没有字符串 URL 编码的方法 Act

  • 如何根据背景图像而不是窗口浏览器来定位图像

    我以前问过这个问题 但似乎没有人明白我在说什么 因为它是书面的 所以我现在只花了 2 分 12 秒 我在视频中说明了我的问题 视频链接 该问题的相关css代码 BackgroundImage position absolute width

  • 加快 Visual Studio 2005 中的编译速度

    对于主要包含 C 项目的解决方案 在 Visual Studio 2005 中加快编译时间的最佳方法是什么 除了预编译标头之外 还有许多其他事情可能会减慢您的速度 病毒检查软件 可能会对构建产生严重影响 如果您正在运行病毒检查程序 请尝试将

  • k-means 的时间复杂度是多少？

    我正在经历k means 维基百科页面 http en wikipedia org wiki K means clustering 根据算法 我认为复杂度是O n k i n 总元素 k 簇迭代次数 那么有人可以向我解释一下维基百科上的这个

热门标签