我想对整数数组进行分区，以便负值位于正值的左侧，并且我想就地执行此操作（无需额外的辅助内存）。请注意，数组不能从小到低排序，只需将负数收集到左侧，将正数收集到右侧。
我创建了一个时间复杂度为 O(n^2) 的朴素函数，但想知道如何在线性时间内解决它？我的算法使用两个指针，开始指向数组的最左边和最右边的元素。当 ptr1 遇到正值，而 ptr2 遇到负值时，我们执行交换，指针向右/向左迭代，当它们相遇时，函数返回，因为数组已完成收集。
你能帮我想出一个更简单的算法来进行这种收集吗？
int* swaps(int* array){
int* ptr1;
ptr1 = &array[0];
int* ptr2;
ptr2 = &array[N-1];
int tmp;
for(ptr1; ptr1 <= &array[N-1]; ptr1++){
if(ptr1==ptr2){
return array;
}
if(*ptr1 >= 0){
for(ptr2; ptr2 >= &array[0]; ptr2--){
if(ptr1==ptr2){
return array;
}
// swap elements
if(*ptr2 < 0){
tmp = *ptr2;
*ptr2 = *ptr1;
*ptr1 = tmp;
ptr2--;
if(ptr1==ptr2){
return array;
}
break;
}
}
}
}
}
我在确定算法的复杂性时遇到了问题，因为它使用了ES6 的功能，当然它们是链式方法。我已经知道这些方法的一些基本复杂性，例如Array.prototype.map 的复杂性是 O(n)。但是当我们想要确定算法的复杂性时，我们如何管理链式方法？
例如，假设我们有一个函数，它返回一个数组的正数之和
let sumPositive = arr => arr.filter(i => i > 0).reduce((a, b) => a + b, 0);
console.log(sumPositive([1, 2, 3, -4])); // 6
console.log(sumPositive([1, 2, 3, 4])); // 10那么，该函数的复杂度是多少？
另一个例子是这个算法，对于给定的字符串，返回字符串中每个字符的计数
let charCount = str => str.split('').map(
(c,_,str) => str.filter(i => i===c)
).reduce((a, b) => a.hasOwnProperty(b[0]) ? a : ({...a, [b[0]]: b.length}), {});
console.log(charCount("hi")); // {"h": 1, "i": 1}
console.log(charCount("hello to you")); // {"h": 1, "e": 1, "l": 2, …str_A ^ str_BOCaml的复杂性是多少？
看看这段代码.
interface ILoader
{
}
interface ILoader<T>: ILoader
{
T Load();
}
class CarLoader: ILoader<Car>
{
...
}
class TrainLoader: ILoader<Train>
{
...
}
class Container
{
List<ILoader> loaders = new ILoader[] { new CarLoader(), new TrainLoader()};
public T Load<T>()
{
// Finding right loader
var loader = loaders.OfType<ILoader<Car>>.FirstOrDefault();
return loader.Load();
}
}
我有大约100个装载机,我需要加载很多火车,汽车等.我认为装载机列表非常慢(有OfType()线性复杂性??),你建议使用什么而不是列表？Dictionary<Type,ILoader>或Hashtable<Type,ILoader>或HashSet<ILoader>？例如使用hashset.OfType<ILoader<Car>>(),列表或更快的速度有多快？
随着查询大小的增长,对数据库的查询很容易在您实际使用的RDBMS中变得难以计算.因此,我想,为了在实践中使用DB(使用DB作为后端进行编程),您必须知道可接受查询的复杂性/大小的界限.
如果编写需要向关系数据库发出复杂查询的程序,那么预期您使用的RDMS有效回答的查询的"最大"大小/复杂性是什么？
对关系数据库系统提出的查询的常规大小是多少？它低于最大界限多少？
提出这个问题的动机是以下理论推测:似乎已知要 在数据库D上找到查询Q的答案,需要时间| D | | Q | ,一个人无法摆脱指数| Q | .(寻找一个集团是最坏情况查询的一个例子.)由于D在实践中可能非常大,我们想知道为什么数据库可以工作.
嗨我使用以下通用冒泡排序算法,我想显示时间复杂度.我知道这个算法的最佳/最坏情况是固定的,但我想知道,它可以特定于我的阵列吗？
例如,这种情况的最坏情况是O(n^2),这可能是我的阵列特有的吗？
例如,最坏的情况是可以对120个元素中的100个进行排序(这就是我的数组特定的含义).
public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
boolean changed = false;
do {
changed = false;
for (int a = 0; a < comparable.length - 1; a++) {
if (comparable[a].compareTo(comparable[a + 1]) > 0) {
E tmp = comparable[a];
comparable[a] = comparable[a + 1];
comparable[a + 1] = tmp;
changed = true;
}
}
} while (changed);
}
下面是我写的一些伪代码,给定一个数组A和一个整数值k,如果A中有两个不同的整数,则返回true,否则返回false.我试图确定这个算法的时间复杂度.
我猜这个算法在最坏情况下的复杂性是O(n ^ 2).这是因为第一个for循环运行n次,并且此循环中的for循环也运行n次.if语句进行一次比较并返回一个值,如果为true,它们都是常量时间操作.最终的return语句也是一个恒定的时间操作.
我猜对了吗？我是算法和复杂性的新手,所以如果我在任何地方出错,请纠正我!
Algorithm ArraySum(A, n, k)
for (i=0, i<n, i++)
for (j=i+1, j<n, j++)
if (A[i]+A[j]=k)
return true
return false
for i = 0 to size(arr)
for o = i + 1 to size(arr)
do stuff here
这是最糟糕的时间复杂性是什么？它不是N ^ 2,因为第二个每i循环减少一个.它不是N,它应该更大.N-1 + N-2 + N-3 + ... + N-N + 1.
我知道heapsort的时间复杂度为O(n log n),但我真的不能想到一个具有O(n(log n)2)的算法.