computational complexity

计算复杂性（computational complexity）指的是在计算机科学中，研究算法的时间和空间复杂度的一门学科。它研究的是在计算机上解决问题所需要的计算资源的量，包括时间和空间。计算复杂性理论的主要目标是研究算法的效率和可行性，以及在不同的计算模型下算法的复杂度。

相关问题

computational complexity sanjeev arora 中文版

《计算复杂性：Sanjeev Arora》是一本深入解析计算复杂性领域的重要著作，该书由计算机科学家Sanjeev Arora撰写。

这本书主要关注计算问题的复杂性理论，并探讨了许多重要的计算难题。计算复杂性是研究计算问题的难度和可解性的一门学科。在现实世界中，许多问题是不易解决的，尤其是当问题规模变大时。通过分析问题的计算复杂性，我们可以判断一个问题是否可行，并且找到解决问题的最好方法。

Arora在书中介绍了一些计算复杂性的基本概念和原则。他介绍了三个重要的计算问题类别：P类、NP类和困难问题。P类包括那些可以在多项式时间内解决的问题。NP类则包括那些可以在多项式时间内验证的问题，但尚未找到快速解决方案。困难问题是那些尚未找到多项式时间解决方案，并且在理论上被认为是难解的问题。

Arora详细介绍了各种计算难题，并提出了一些重要的研究方向，例如近似算法和证明等。近似算法是在有限时间内找到问题的次优解的研究。证明则是使用数学技术来论证问题的复杂性和可解性。

这本书是一部重要的参考资料，适用于计算机科学家、研究人员和学生。它提供了一个深入的理论基础，使读者能够更好地理解和解决计算复杂性问题。这本书的贡献在于它的全面性和剖析良好的讲解方式。无论是理论研究还是实际应用，这本书都为我们提供了有价值的洞察和指导。

The K-Medoid Clustering Method • K-Medoids Clustering: Find representative objects (medoids) in clusters • PAM (Partitioning Around Medoids, Kaufmann & Rousseeuw 1987) • Starts from an initial set of medoids and iteratively replaces one of the medoids by one of the non-medoids if it improves the total distance of the resulting clustering • PAM works effectively for small data sets, but does not scale well for large data sets (due to the computational complexity) • Efficiency improvement on PAM • CLARA (Kaufmann & Rousseeuw, 1990): PAM on samples • CLARANS (Ng & Han, 1994): Randomized re-sampling翻译并解释

这段文字介绍了一种叫做K-Medoid聚类方法，其目标是在聚类中找到代表性对象（medoids）。其中，PAM（Partitioning Around Medoids）是一种常用的K-Medoid聚类算法，其通过从初始medoids集合开始，迭代地将一个medoid替换为一个非medoid对象，以改善聚类结果的总距离。然而，PAM在处理大数据集时效率较低，因为其计算复杂度较高。

为了提高效率，研究者们提出了一些改进方法。例如，CLARA（Kaufmann和Rousseeuw，1990）是在样本数据上运行PAM的一种方法；而CLARANS（Ng和Han，1994）是一种随机重采样方法，旨在更快地找到合适的medoids。总的来说，K-Medoid聚类方法是一种常用的聚类算法，能够有效地处理小型和中型数据集。