个人中心
文章发布
退出
作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误，当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
26
4
我正在类里面研究算法的复杂性，我需要知道是否还有其他算法的复杂性，我所知道和研究的是两种类型1- 是 BIG O 的复杂性，即时间和性能以及其他2- 是空间复杂度，也就是内存复杂度，算法有任何其他类型的复杂性吗？算法是否由我错过的其他任何东西来衡量？
最佳答案
就算法的渐近复杂性而言 - 是的，算法(和问题)是根据空间和时间来衡量的。
但是，关于它我还有很多话要说。我将尝试解决一些问题:
空间/时间消耗来自分析方法
算法的常用分析方法有4种，用于空间和时间。请记住 big-O 是一组函数，但是如何导出函数？复杂度的函数是根据分析方法导出的，(通常)是以下之一:
这些方法中的每一种都可以用于任何算法 - 并且不能保证结果相同。例如，快速排序具有 O(n^2) 最坏情况时间复杂度和 O(nlogn) 平均情况时间复杂度。
更多集:
除了大O符号外，我们还使用其他符号来表示复杂度。其他常用符号是(按用法的通用性):
不要与分析方法混淆:Big Theta/Big O/符号中的每一个...都可以与任何分析方法配对(最坏情况/平均情况/...)
更多关于Big Theta、Big O的细节以及它们之间的区别可以在this thread中找到。
理论复杂性:
在理论领域"Complexity Theory" - 我们分析问题，而不是算法。在这个领域，我们关心的是一个问题是否可以多项式求解(也就是说，如果输入的大小为 n，那么这个问题可以用 n 的某个幂来求解) ), 多项式验证(给定一个可能的解决方案，检查它是否正确)。但是，还有其他类。
常见的复杂度类有:
此外——我们对问题是否可解/可判定感兴趣。描述问题可解决性的常见类有:
现实世界:
在现实世界的应用程序中——我们不仅关心理论上的空间/时间复杂度，还关心常量(一种算法花费的时间是另一种算法的一半要好得多，即使它们可以属于相同的复杂度等级. 这是因为复杂性类忽略常量。)。
我们还考虑了程序/算法的实现时间和可维护性。
关于算法复杂度性能和空间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13009258/
26
4
0
多数元素问题: Given an array of size n, find the majority element. The majority element is the element tha
我有一个简单的问题来找到数组 A 中的第一个唯一元素。但是，令我困扰的是使用不同方法的时间复杂度。到目前为止，我已经尝试过这两种方法。 第一种方法: LinkedHashMap> map = new
STL 中valarray::min 和valarray::max 函数的时间复杂度是多少？ 此外，什么是查找各种其他 STL 组件的时间/空间复杂性的良好来源？ 最佳答案 O(N) 这些函数不会缓存
我目前正在学习复杂性(或效率，不管你怎么调用它)，我在我得到的一本书中读到了它。写了一些我觉得很无意义的东西，我需要一个解释。我试过在线查找，但我没有找到他们给出的这个特定示例的答案。 For an
如何分析算法？是什么让快速排序具有 O(n^2) 的最坏情况性能，而合并排序具有 O(n log(n)) 的最坏情况性能？ 最佳答案 这是整个学期的主题。最终，我们讨论的是在算法完成之前必须完成的操作
有谁知道最流行的数据库的 SQL LIKE 运算符的复杂度是多少？ 最佳答案 让我们分别考虑三个核心案例。此讨论是特定于 MySQL 的，但也可能适用于其他 DBMS，因为索引通常以类似的方式实现。
Go 编程语言中这个循环的计算复杂度是多少？ var a []int for i := 0 ; i doublecap { newcap = cap } else {
我需要创建一个查找函数，其中 (X,Y) 对对应于特定的 Z 值。对此的一个主要要求是我需要尽可能接近 O(1) 复杂度。我的计划是使用 unordered_map。 我通常不使用哈希表进行查找，因为
快速提问，主要满足我对该主题的好奇心。 我正在编写一些带有 SQlite 数据库后端的大型 python 程序，并且将来会处理大量记录，因此我需要尽可能优化。 对于一些功能，我正在通过字典中的键进行搜
Go 编程语言中这个循环的计算复杂度是多少？ var a []int for i := 0 ; i doublecap { newcap = cap } else {
我有这个方法: public static int what(String str, char start, char end) { int count=0; for(int i=0;
for (i = 0; i i; j--) //some code that yields O(1) } 我认为上面的代码会产生 n*log(n) 但我看到另一个消息来源说它真的是 n^2
我对 InnoDB 中 OFFSET 的复杂性有疑问。我知道这主要适用于线性复杂性，但如果我在字段上有索引？! 示例: CREATE TABLE `person_rand` ( `p_id` int
我嵌套了一些 if/else 语句，但我想减少它们的开销。 在示例中，我正在评估从哪个下拉列表中单击了 li 项目，以及该 li 项目是否是第一个 (currentIndex === 0)。 代码:
这是我的第一个问题，所以我希望我没有违反任何规则。我终于设法为基数排序算法编写代码，但我想知道我是否做错了。让我觉得我的算法看起来复杂度为 O(n^3)，但众所周知，基数排序是一个 O(k.n) 算法
几周前我认识了 big-O 并试图掌握它，但是尽管有很多关于计算时间复杂度的 Material ，但我似乎无法找到如何使算法更高效。 我一直在练习 Codility 中的演示挑战: Write a f
在最近的一次考试中，我们得到了一个函数来计算在未排序的 ArrayList 中出现了多少个 double (不是原始 double，而是一个项目出现两次的次数)。 我正确地确定了 Big O 复杂度为
以下循环的大 O 复杂度是多少: for each vertex u ∈ C do for each vertex v ∈ C and v > u do 我在这里做的是想象以下集合 {
我想对条款进行排序，使每个条款都是下一个条款的大 O √n√logn √n log( n^30) n/〖(logn)〗^2 〖16〗^(log√n) 谁能帮忙找到顺序？ 最佳答案 claim :16
我正在尝试计算此选择排序实现的大 O 时间复杂度: void selectionsort(int a[], int n) { int i, j, mini
我是一名优秀的程序员,十分优秀！