标签: time-complexity

任何人都可以解释以下Dictionary方法的复杂性是什么？

ContainsKey(key)
Add(key,value);

我想弄清楚我写的方法的复杂性:

public void DistinctWords(String s)
{
    Dictionary<string,string> d = new Dictionary<string,string>();
    String[] splitted = s.split(" ");
    foreach ( String ss in splitted)
    { 
        if (!d.containskey(ss))
            d.add(ss,null);
    } 
}

我假设2个字典方法具有log(n)复杂度,其中n是字典中的键数.它是否正确？

我为旅行商问题编写了一个强力搜索算法,并对其进行了测试,以查看各种"城市"所需的时间.从下面的图中,我们可以看到,时间大约是成正比的(n-1)!地方n是"城市"的数量.它与n!(毕竟(n-1)! = n! / n)不成正比.

我的问题是,说算法运行是否仍然正确O(n!),或者说我更好O((n-1)!)吗？我以前从未见过后者,但似乎更准确.看来我在这里误解了一些东西.

[t =所用时间,n =城市数量]

我正在研究一个 HackerRank 问题，该问题在反转行和列后找到 2N x 2N 矩阵的左上象限中元素的最大总和。例如，如果矩阵是

M = [
  112  42   83   119
  56   125  56   49
  15   78   101  43
  62   98   114  108
];

那么将行和列颠倒后可以形成的最大和就是119 + 114 + 56 + 125 = 414得到矩阵后

M' = [
   119  114  42   112
   56   125  101  49
   15   78   56   43
   62   98   83   108
];

反转第 2 列和第 0 行。

我还没有找到一个简单的解决方案，但我提出了一些可能有用的事实：

• 不可能通过反转行和列来获得任何配置。因此，答案不能是简单地对所有元素进行排序并对NxN它们的顶部求和。
• 此外，不可能将任何 1 个元素移动到任何其他位置。例如，(N-1,N-1)处的元素唯一可能被移动的位置是(0,N-1),(N-1,0),(0,0)。
• 从右上象限或左下象限到左上象限需要进行 1 次行反转，从右下象限到左上象限需要进行 2 次反转。
• 不可能提出一个简单地查看左上象限中的每个元素并检查它是否可以被可移动到其位置的元素范围内的更大元素替换的解决方案（例如可以替换M[0,1]=42为 …

对于基本算术运算的广泛算法,如乘法,平方根,对数,标量和矩阵乘积,Big-O复杂度是多少？

在Big-O复杂性方面是否存在更高效的外来算法,但在实际解决方案中并不是非常普遍(例如,在流行的软件库中没有实现)？

我实现了这个功能,power()这需要两个参数a和b并计算^b.

typedef long long int LL;

LL power(int a,int b)
{
   int i = 1;
   LL pow = 1; 
   for( ; i <= b ; ++i )
     pow *= a;
   return pow;
}

鉴于:a ^b属于范围long long int.
问题:如何降低算法的时间复杂度？

我开始学习时间复杂性,我在实例中查看了一些简单的时间复杂度.

我想知道我们如何计算平均时间复杂度为一个图表,深度优先搜索|V|=n和|E|=m,让起始节点是"U"和终端节点是"V".

我使用Backtracking方法在c ++中编写骑士游览算法.但它似乎太慢或陷入无限循环n> 7(大于7乘7棋盘).

问题是:该算法的时间复杂度是多少？如何优化它？!

骑士之旅的问题可以说明如下:

给定一个有n×n方格的棋盘,找到一个骑士的路径,每个方格只访问一次.

这是我的代码:

#include <iostream>
#include <iomanip>
using namespace std;

int counter = 1;
class horse
{
public:
  horse(int);
  bool backtrack(int, int);
  void print();
private:
  int size;
  int arr[8][8];
  void mark(int &);
  void unmark(int &);
  bool unvisited(int &);
};

horse::horse(int s)
{
  int i, j;
  size = s;
  for(i = 0; i <= s - 1; i++)
    for(j = 0; j <= s - 1; j++)
      arr[i][j] = 0;
} …

我需要分析Java中某些算法的复杂性.为此,我计划提供大量输入并测量Java实现所花费的时间.检查某些代码行之间的时间最准确,最准确的方法是什么？我需要精确到毫秒......

我正在看这个pycon谈话,34:30,发言人说,获取t元素列表中最大的n元素可以完成O(t + n).

怎么可能？我的理解是创建堆将是O(n),但nlargest它本身的复杂性是它O(n + t)还是O(t)(以及实际算法是什么)？

我有这个函数来确定列表是否是另一个列表的轮换:

def isRotation(a,b):
  if len(a) != len(b):
    return False

  c=b*2
  i=0

  while a[0] != c[i]:
    i+=1

  for x in a:
    if x!= c[i]:
      return False
    i+=1

  return True

例如

>>> a = [1,2,3]
>>> b = [2,3,1]
>>> isRotation(a, b)
True

如何使用重复项进行此操作？例如

a = [3,1,2,3,4]
b = [3,4,3,1,2]

它可以及时完成O(n)吗？