标签: time-complexity

我写了以下课程:

public class SortingObjectsWithAngleField implements Comparator<Point> {  
    public int compare(Point p1, Point p2) {
        double delta = p1.getAngle() - p2.getAngle();
        if(delta == 0.00001)
            return 0;
        return (delta > 0.00001) ? 1 : -1;
    }
}

然后,在我的main()方法中,我创建了一个List我添加了一些具有"X"和"angle"字段的对象.

然后我用:

Collections.sort(list, new SortingObjectsWithAngleField());

这种排序方法的复杂性是什么？

我有一个大型数据库(可能在数百万条记录中),文本串相对较短(按街道地址,名称等顺序排列).

我正在寻找一种去除不精确重复的策略,模糊匹配似乎是首选方法.我的问题:许多文章和SO问题涉及将单个字符串与数据库中的所有记录进行匹配.我希望立即对整个数据库进行重复数据删除.

前者是线性时间问题(将值与一百万个其他值进行比较,每次计算一些相似性度量).后者是一个指数时间问题(将每个记录的值与每个其他记录的值进行比较;对于一百万条记录,这与前一个选项的1,000,000次计算相比,大约为5 x 10 ^ 11次计算).

我想知道是否有另一种方法,而不是我提到的"蛮力"方法.我想可能生成一个字符串来比较每个记录的值,然后对具有大致相等的相似性度量的字符串进行分组,然后通过这些组运行暴力方法.我不会达到线性时间,但它可能有所帮助.此外,如果我正确地考虑这一点,这可能会错过字符串A和B之间潜在的模糊匹配,因为它们与字符串C(生成的校验字符串)的相似性尽管彼此非常相似但是非常不同.

有任何想法吗？

PS我意识到我可能在时间复杂度上使用了错误的术语 - 这是一个我基本掌握的概念,但不够好,所以我可以在现场将算法放入适当的类别.如果我使用了错误的术语,我欢迎更正,但希望我至少得到了我的观点.

编辑

一些评论者提出,鉴于记录之间的模糊匹配,我的策略是选择要删除哪些(即给出"foo","boo"和"coo",这将被标记为重复并删除).我应该注意,我不是在寻找自动删除.其目的是在6000万个记录数据库中标记可能的重复数据,以供人工审查和评估之用.如果有一些误报,可以,只要它是一个大致可预测/一致的数量.我只需要了解复制品的普遍程度.但是如果模糊匹配传递需要一个月才能运行,那么这首先不是一个选项.

为什么c ++的实现string::find()不使用KMP算法(并且不运行O(N + M))并运行O(N * M)？这是在C++ 0x中纠正的吗？如果当前查找的复杂性不是O(N * M),那是什么？

PS:对不起,我的意思是 O(N * M)

那么在gcc中实现了什么算法？是KMP吗？如果没有,为什么？我测试了它,运行时间表明它运行了string::find()

我只想知道,当后缀树优于增强后缀数组时.

在阅读了使用增强的suf fi x数组替换suf fi x树之后,我再也看不到使用后缀树的理由了.有些方法可能会变得复杂,但您可以使用后缀数组执行所有操作,使用后缀树可以执行的操作,并且需要相同的时间复杂度但内存较少.

一项调查甚至表明,后缀数组更快,因为它们缓存更友好,并且不会产生更多的缓存未命中,然后产生后缀树(因此缓存可以更好地预测数组使用,然后在递归树结构上).

那么,有没有人知道在后缀数组上选择后缀树的原因？

编辑 好的,如果你知道更多告诉我,到目前为止:

• 后缀不允许在线构造
• 一些模式匹配算法在Suffixtrees上运行得更快
• (补充)由于在线构造,你可以将它保存在高清上并扩大现有的后缀树.如果你使用SSD,它也应该安静快速.

我已经读过一个集合中的插入操作只需要log(n)时间.怎么可能？

要插入,首先我们在排序数组中找到新元素必须位于的位置.使用二进制搜索需要log(n).然后要插入该位置,其后面的所有元素都应该向右移动一个位置.这需要另外n次.

我怀疑是基于我的理解,set是作为数组实现的,元素是按排序顺序存储的.如果我的理解是错误的,请纠正我.

给出一个清单:

List<object> SomeList = new List<object>();

做:做

SomeList.Insert(i, val);

比.

SomeList.Add(val);

有任何性能损失？如果是的话,它取决于:
- i- 插入索引
- SomeList.Count- 列表的大小

我一直在阅读关于稀疏PCA的论文,其中包括:http: //stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf

并且它表明,如果你有n数据点,每个数据都用p功能表示,那么,PCA的复杂性就是O(min(p^3,n^3)).

有人可以解释一下/为什么？

我有一个需要用O(n)时间复杂度完成的练习,但是,我只能用O(n ^ 2)解决方案解决它.

你有一个数组,你需要计算最长的连续序列,使得它的总和可以被分成3而没有任何余数.例如array {1,2,3,-4,-1),函数将返回4,因为它sum(0)可以被分成的最长序列3是{2,3,-4,-1}.

我的解决方案O(n ^ 2)基于arithmetic progression.有没有办法用O(n)复杂度做到这一点？

拜托,我只想要一个线索或理论解释.请不要写完整的解决方案:)

这是Cracking the Coding Interview(第5版)中Fibonacci序列的递归实现

int fibonacci(int i) {
       if(i == 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonaci(i-2);
}

在观看关于该算法的时间复杂度的视频后,斐波纳契时间复杂度,我现在理解为什么该算法在O(2 ⁿ)中运行.然而,我正在努力分析空间复杂性.

我在网上看了一下这个问题.

在这个Quora线程中,作者声明"在你的情况下,你有n个堆栈帧f(n),f(n-1),f(n-2),...,f(1)和O(1 )".你不会有2n堆栈帧吗？说f(n-2)一帧是实际的呼叫f(n-2),但是f(n-1)也不会有呼叫f(n-2)？

我试图回答以下问题:你有一个整数数组,这样每个整数都有一个奇数个时间,除了3个.找到三个数字.

到目前为止,我带来了蛮力方法:

 public static void main(String[] args) {
    // TODO Auto-generated method stub

    int number[] = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };
    FindEvenOccurance findEven = new FindEvenOccurance();
    findEven.getEvenDuplicates(number);

  }

  // Brute force
  private void getEvenDuplicates(int[] number) {

    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    for (int i : number) {

      if (map.containsKey(i)) {
        // a XOR a XOR a ---- - -- - - odd times = …