我想要一些帮助来解决我在教科书中发现的以下问题。
sort (array[], nr_of_item)
{
while(true)
i:=value from an n-sided fair dice roll
j:=value from an n-sided fair dice roll
if (i > j)
swap i and j
if (array[i] > array [j])
swap array[i] and array[j]
end while
}
现在,它说它没有描述一个正确的算法
我的问题是,有没有可能将(未知数量的数组)合并成一个数组?我不知道确切的数组数量(不像合并两个数组合并n个array.so等)。签名:
> int [] merge(int k)//k is number of arrays to be merged into a one
> merge them
//and so on..
>
> return array;
我正在尝试设计一种算法来查找数组中两个相同元素的索引。输入是一个数组,输出是两个索引i&j,使得arrayi=arrayj。时间复杂度必须为O(nlogn)。
这是我尝试过的
let i=0 to size_of_array{
let j=i+1 to size_of_array{
if array[j]=array[i]{
print(i, j)
}
}
}
嵌套循环是O(n^2),但如果我尝试这样设计。时间复杂度是多少?
N是数组的大小,我的实现将运行O(n(n-1)+(n-2)+(n-3)....+1)次。它
下面的方法在未排序的数组中查找整数的最长连续序列。({1,3,2,4,6,5}将返回6):
public static int what(int[] vec) {
int m = 0;
for (int i = 0; i < vec.length; i++) {
int c = 0;
int n = i;
do {
n = find(vec, vec[n]+1);
c++;
} while (n != -1);
if (c > m)
给定一个由n个元素组成的数组和数组中的一个元素x,有没有一种快速的方法可以在不排序的情况下找到x的秩?
由于我现在处理的是一个非常大的数组,O(n)时间复杂度的算法对我来说仍然太慢了,这就是为什么我试图寻找排序之外的其他选择。
编辑:
所以现在我的算法类似于:
for x in list:
A = x.dot(B) ## return a numpy array
rank = findRank(a, A) ## find the rank of a in A
doSomething2(rank)
所以这里我的瓶颈是findRank(),在我当前的实现中,我首先对数组进行
我们的老师没有教我们如何分析算法的运行时间,然后她想让我们报告Shell排序。
我只想知道是否有一种简单的方法可以找到像shell排序这样的算法的平均/最佳/最坏情况的性能。
//for references
class ShellSort{
void shellSort(int array[], int n){
//n = array.length
for (int gap = n/2; gap > 0; gap /= 2){
for (int i = gap; i < n; i += 1) {
int temp = array[
我的职能如下:
function myFunction(array, sum){
for(var i = 0; i < array.length; i++){
var firstValue = array[i];
for(var x = i + 1; x < array.length; x++){
var secondValue = array[x];
if((firstValue + secondValue) == sum){
我给出了两个不同时间复杂度的for循环示例。一个是二次的,另一个是对数的。谁能告诉我为什么时间复杂度不同,因为两个代码迭代的次数相同,但操作不同?
时间复杂度的因素是什么?次数还是操作?
//Quadratic O(n^2)
var c = 0
for i in 1...100{
c = Int(pow(Double(i), 2))
}
//Logarithamic O(log n)
var d = 0
for i in 1...100{
d = Int(log(Double(i)))
}
我有两个数组
let a1 = [obj1, obj2, obj3]
let a2 = [obj3, obj2, obj1]
假设数组元素是自定义对象,它们是,而不是可排序的。我只想检查Arrays是否按任何顺序包含相同的元素。
我试过这个:
if a1==a2 { print("S1 is the same as S2") }
else { print("S1 is not the same as S2") }
但我得到的输出是"S1与S2不一样“。
我所能想到的只有两个解决方案
排序和比较(如果元素不可排序,例如复数),则不起作用。
从另一个
我试图了解是否有任何替代蛮力算法(或轻微的改进/最坏的性能比幼稚的蛮力算法)仍然将导致O(N^2)的时间复杂性和O(1)辅助空间。
这是我的蛮力伪码:
procedure distinct(Input: array)
for i=0 to i < length of array
for j=i+1 to j < length of array
if array[i] ==
我正在尝试使用时间复杂度的渐近表示法。我知道big-O是上限,theta是一个严格的界限,但我对何时使用哪一个感到困惑,以及为什么有时会给出一个而不是另一个。 具体来说,对于下面给出的同一算法的三个实现,作者分别描述了平均时间复杂度为O(n²),Ө(nlogn)和Ө(n)。 我想知道在进行这些任务时,这些问题的专家在想些什么。为什么第一个拳头是大O,而其他两个是θ,为什么最后一个提到平均情况,而其他两个没有? 任何帮助都非常感谢。 def RemoveDuplicates(A):
m = 0
for i in range(0, len(A)):
if (not
我的任务有点麻烦;我的任务是想出我自己的解决方案来解决煎饼问题。
我已经完成了大部分代码,除了这一部分(下面是伪代码):
//assuming input is an array of [0...n-1] size
int maxValue = -infinity
for int i <- 0 to n-1 do
{
for int j <-i to n-1 do
{
if A[j] > maxValue
{
maxValue <- A[j]
maxPos <- j
if
我有一个函数,它将网格中一系列点的所有邻居拉出到一定的距离,这涉及到许多重复项(我邻居的邻居再次== me )。
我已经尝试了几种不同的解决方案,但我不知道哪种更有效。下面的代码演示了两个并行运行的解决方案,一个使用std::vector sort- one erase,另一个使用std::copy into a std::unordered_set。
我还尝试了另一种解决方案,那就是将包含邻居的向量传递给neighbour函数,该函数将使用std::find来确保邻居在添加之前不存在。
所以有三个解决方案,但我不能完全理解哪一个会更快。有没有人有主意?
代码片段如下:
// Vector o