标签: divide-and-conquer

我需要计算列表中字符串之间的余弦相似度.例如,我有一个超过1000万个字符串的列表,每个字符串必须确定它自己与列表中的每个其他字符串之间的相似性.什么是我可以用来有效和快速完成这项任务的最佳算法？分而治之算法是否适用？

编辑

我想确定哪些字符串与给定字符串最相似,并且能够获得与相似性相关的度量/分数.我认为我想做的事情与群集相符合,群集的数量最初并不为人所知.

以下问题取自算法问题(问题653):

你被给予了2个数字矩阵.找到一个O(n log n)算法,该算法置换数组中的行,使得数组中的任何一列都不包含比⌈√n更长的子序列(可能不包含连续的数组元素).

我不知道如何解决这个问题.我认为它可能会使用某种分而治之的复发,但我似乎无法找到它.

有没有人有任何想法如何解决这个问题？

我已阅读无处不在,对于分而治之的排序算法像Merge-Sort和Quicksort,而不是递归,直到只有一个元素是左,这是更好地转移到Insertion-Sort时候一定阈值,比如30元,达到.那很好,但为什么只有Insertion-Sort？为什么不,Bubble-Sort或Selection-Sort两者都有类似的O(N^2)表现？Insertion-Sort只有当许多元素被预先排序时才应该派上用场(虽然这个优势也应该附带Bubble-Sort),但除此之外,为什么它应该比其他两个元素更有效？

其次,在这个链接中,在第二个答案及其附带的评论中,它表示O(N log N)与O(N^2)最高级别相比表现不佳N.怎么会？N^2应该总是表现得比N log N,因为N > log N对于所有N> = 2,对吧？

数字1到n以指定顺序p_1,p_2,...,p_n插入二叉搜索树中.描述一个O(nlog n)时间算法来构造最终的二进制搜索树.

注意 :-

1. 我不需要平均时间n log n,但是最差的时间.
2. 我需要使用通常的规则进行插入时产生的确切树.不允许AVL或红黑树.

这是一个作业问题.这非常非常重要.事实上,乍一看似乎是不可能的.我已经考虑过了很多.我的观察: -

1. 我们用来证明排序至少花费n log n时间的论点并没有消除这种算法的存在.
2. 如果总是可以在O(n)时间内找到一个子树,其大小在树的两个分数之间,则问题可以很容易地解决.
3. 选择root的中位数或左子项作为子树的根不起作用.

标题是这样的问题.我试图弄清楚是否有一种在O(n)时间内在2d阵列中找到峰值元素的方法,其中n是2d阵列中每一侧的长度,即n ^ 2个总元素.

根据定义,2-d数组中的"峰值"是一个元素,使得它对所有邻居(即上,下,左和右时隙中的元素)> =.

我在以下网址阅读课程说明:http: //courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf, 并了解如何在O(nlogn)中做,但似乎没有完全掌握如何处理O (N).

任何人都可以提出或解释这个问题在O(n)中如何解决？

编辑:n是数组每一边的长度,即总共有n ^ 2个元素.

我有一个关于编程算法中的分而治之的问题。假设你在 Python 中得到一个随机整数列表，它包括：

1. 唯一连续的整数对
2. 列表中某处的单个整数

并且条件是排他的，这意味着虽然[2,2,1,1,3,3,4,5,5,6,6]有效，但这些不是：

1. [2,2,2,2,3,3,4] （违反条件1：因为有两对2，而任何数字最多只能有一对）
2. [1,4,4,5,5,6,6,1] （违反条件 1：因为有一对 1 但它们不连续）。
3. [1,4,4,5,5,6,6,3] （违反条件2：有2个单号，1和3）

现在的问题是你能在 O(lgn) 算法中找到“单个”数字索引吗？

我原来的刺拳是这样的：

def single_num(array, arr_max_len):

  i = 0

  while (i < arr_max_len):
    if (arr_max_len - i == 1):
      return i
    elif (array[i] == array[i + 1]):
      i = i + 2
    else:
      return i # don't have to worry about odd index because it will never happen
  
  return None 

然而，该算法似乎以 O(n/2) 的时间运行，这似乎是它所能做的最好的。

即使我使用分而治之，我也不认为它会比 O(n/2) 时间更好，除非有一些方法超出了我目前的理解范围。

任何人都有更好的主意，或者我可以说，这已经是 O(log n) 时间了吗？

编辑：似乎 Manuel …

我找到了解决此任务的一个问题.

你有N个学生和N个课程.学生只能参加一门课程,许多学生可以参加一门课程.如果他们参加同一课程,两名学生是同学.如何找出N学生中是否有N/2名同学？

条件:你可以带两个学生,问他们是不是同学,只有你可以得到的答案是"是"或"否".你需要在O(N*log(N))中执行此操作.

我只需要知道如何制作它,伪代码就可以了.我想它会将学生列表分成合并排序,这给了我复杂性的对数部分.任何想法都会很棒.

据我所知,该算法使用8次乘法和4次加时间复杂度:

乘法在每个n/2 * n/2矩阵上完成.我对此几乎没有问题:

1. 每个n * n矩阵最终都会n=1通过执行来缩小尺寸T(n/2)吗？如果这样返回a11*b11似乎毫无意义好像回到1*6了a11*b11为以下矩阵:

然后基本情况应该n==2执行else部分,因为下面的操作似乎是合法的.

2. 为什么增加部分采取0(n^2)？我的意思是,我们完全没有处理矩阵加法,而仅仅是数字,因为每个矩阵都减少到2 * 2如下:

那么加法部分应该只贡献4个？(为什么0(n^2)？)

一个×棋盘将切入其单位正方形.在每个步骤中,您可以进行一次水平切割或一次垂直切割.第一次切割会将电路板分成两个子板; 之后,每次切割将一个剩余的子板分成两个.削减成本等于两个所得子板中较小的剩余单位平方数.例如,2×3板上的水平切割产生两个1×3子板并且成本为3,而垂直切割产生尺寸为2×1和2×2且成本为2的子板.成本是附加的:一系列削减的成本等于其个人成本的总和.描述一种算法,用于计算将×板减少到单位平方的最小总成本.证明其正确性并展示您对其时间复杂性的分析.

我的解决方案如下:1.我遵循贪婪的方法,检查m(行)和n(列)之间的最高点并进行切割.2.如果m更高,我会做一个垂直切割而另一个是水平切割.这给了我每一步的最低成本.我遵循分而治之,并递归地遵循方法,直到我有mxn = 1 x 1

这似乎是有效的,但我正在努力的是得出时间复杂度并证明我的算法的正确性.

我的时间复杂度表达式是T(m n)= 2 T(m n/2)+ theta(n).

有人可以建议我怎么做吗？

当我运行这段代码时，它在java中返回“退出状态143”，我不知道那里出了什么问题，希望有人能帮助我解决这个问题。

class Main {
    static double diff(double y, double x, double d){
     if((y*y*y)+d>x)
     return ((y*y*y)+d-x);
     else return(x-(y*y*y)+d);
    }

    static double cubicRoot(double x, double d){
      double start=0 , end=x;
      double e = 0.01;
      while(true){
        double y=(start+end)/2;
        double error = diff(x,y,d);
        if (error <= e)
        return y;
        if(y*y*y+d>x)
        end =y;
        else 
        start =y;
      }
    }

      public static void main(String[] args) {

        double x =10;
        double d =0.1;
        System.out.println("root y is:" + cubicRoot(x,d));

      }
    }