1
голосов
4ответов
1352 просмотров

Which Java collection's Linked list adds in O(1) when given an element?

i need to insert into a very large LinkedList, whose elements i hold in a fast-access HashMap. it's important to keep the list in order (which is not the natural order of the keys). i thought it would be possible to hash the linked list nodes, then insert directly on the node (getting the node f...

-2
голосов
3ответов
324 просмотров

Complexity class

Assume that methods m1 and m2 are static void and compute the same result by processing an argument of type Object[]. Empirically we find that m1 -> T(N) = 100N and m2 -> T(N) = 10Nlog2N where the times are in microseconds. For what size inputs is it better to use m1 and m2? So I would use...

1
голосов
3ответов
241 просмотров

Complexity of a given function

When I analyzed the complexity of the code segment below, I found that it is O(n/2). But while searching the internet I discovered that it is probably O(n). I'd like to know who's correct. void function(int n) { int i = 1, k = 100; while (i < n) { k++; i += 2; } }

96
голосов
7ответов
38312 просмотров

Is Big O(logn) log base e?

For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarithm? Sorry for the simple question but I've always had trouble distinguishing between the differ...

0
голосов
4ответов
3164 просмотров

Java How do you find a complexity class for algorithms?

I have a question to find a complexity class estimate of a algorithm. The question gives recorded times for an algorithm. So, do I just average out the times based on how it was computed? Sorry, I missed a part. ok, so it recorded time like N = 100, Algorithm = 300, next N = 200, Algorithm = 60...

0
голосов
3ответов
261 просмотров

Number of sequences over {0,1} such that sequence contains at least half ones

How to calculate number of sequences over {0,1} such that each sequence contains at least half ones?

96
голосов
13ответов
134706 просмотров

What's the fastest algorithm for sorting a linked list?

I'm curious if O(n log n) is the best a linked list can do.

0
голосов
1ответов
142 просмотров

Avoiding O(n) queries with Django

I've got models like this: class PledgeItem(models.Model): title = models.CharField(...) usd_amount = models.DecimalField(...) class Pledger(models.Model): name = models.CharField(...) ... class Pledge(models.Model): pledger = models.ForeignKey(Pledger) item = models...

188
голосов
34ответов
179678 просмотров

How to find the lowest common ancestor of two nodes in any binary tree?

The Binary Tree here is may not necessarily be a Binary Search Tree. The structure could be taken as - struct node { int data; struct node *left; struct node *right; }; The maximum solution I could work out with a friend was something of this sort - Consider this binary tree : T...

24
голосов
11ответов
13142 просмотров

Can a program output a copy of itself

I think this might be a classic question but I am not aware of an answer. Can a program output a copy of itself, and, if so, is there a short program that does this? I do not accept the "empty program" as an answer, and I do not accept programs that have access to there own source code. Rather, ...

7
голосов
4ответов
4338 просмотров

Memory-efficient way of computing the median of a large data set?

If one computer can only hold 1 million numbers, how to find out the median number from 100 million numbers?

3
голосов
11ответов
416 просмотров

How to find all brotherhood strings?

I have a string, and another text file which contains a list of strings. We call 2 strings "brotherhood strings" when they're exactly the same after sorting alphabetically. For example, "abc" and "cba" will be sorted into "abc" and "abc", so the original two are brotherhood. But "abc" and "aaa"...

1
голосов
4ответов
836 просмотров

What is the tersest/densest commonly-used programming language currently available?

I refer you to the following video, which describes how to implement Conway's Game of Life in APL, using a few dozen keystrokes: http://www.youtube.com/watch?v=a9xAKttWgP4 This video was featured prominently in the Return of Uncle Bob Martin podcast, in which Scott Hanselman complains that "his...

2
голосов
2ответов
264 просмотров

Designing an OO and Unit Test Friendly Query System

I'm working on an application that allows dentists to capture information about certain clinical activities. While the application is not highly customizable (no custom workflows or forms) it does offer some rudimentary customization capabilities; clients can choose to augment the predefined fo...

0
голосов
8ответов
5708 просмотров

For loop construction and code complexity

My group is having some discussion and strong feelings about for loop construction. I have favored loops like: size_t x; for (x = 0; x < LIMIT; ++x) { if (something) { break; } ... } // If we found what we're looking for, process it. if (x < LIM...

10
голосов
3ответов
7908 просмотров

Uses of Ackermann function?

In our discrete mathematics course in my university, the teacher shows his students the Ackermann function and assign the student to develop the function on paper. Beside being a benchmark for recursion optimisation, does the Ackermann function has any real uses ?

4
голосов
1ответов
283 просмотров

Effect of memory usage in the complexity of an algorithm

I am reading Nicolai Josuttis book on C++STL algorithms. For many algorithms such as stable_sort(), he mentions that the complexity of the algorithm n * log(n) if enough memory is available, otherwise it is n * log(n) * log(n). My question is how does the memory usage affects the complexity ? And...

4
голосов
5ответов
517 просмотров

Complexity of this function?

void compute(int n) { int h = n; while (h > 1) { for (int i = 0; i < n; i++) { // do some operation } h = h / 2; } } Can anybody please tell me what is the complexity( Big O ) of this function of n ?? This is ac...

2
голосов
2ответов
1096 просмотров

What is the benefit of Xcode's seemingly over-complicated control/outlet workflow?

I'm new to Objective-C, Cocoa, Xcode and Interface Builder. I've got some C background in the past, as well as a fair amount of RealBASIC experience. I'm working through Mark and LaMarche's iPhone 3 Dev book and I'm really just sort of stunned about how tedious some things are. Maybe someone can...

4
голосов
12ответов
2105 просмотров

Strings joining and complexity?

When I need to join two strings I use String.Format (or StringBuilder if it happens in several places in the code). I see that some good programmers doesn't give attention to strings joining complexity and just use the '+' operator. I know that using the '+' operator make the application to use...

4
голосов
2ответов
3411 просмотров

How Prim's algorithm time complexity is ElogV using Priority Q?

Pseudo code which I used: for all V vertices: visited[n]=0 pick any vertex r from graph and set visited[r]=1 For all edges e incident to r PQ.insert() while(PQ is not empty)//line 1 f=PQ.min()//f(r,s) is such that visited[s]=0 for all edges e(s,t) incident to s//line 2 if(visited...

27
голосов
1ответов
8051 просмотров

Understanding Ukkonen's algorithm for suffix trees

I'm doing some work with Ukkonen's algorithm for building suffix trees, but I'm not understanding some parts of the author's explanation for it's linear-time complexity. I have learned the algorithm and have coded it, but the paper which I'm using as the main source of information (linked bellow...

5
голосов
1ответов
7950 просмотров

Banker's algorithm calculated time complexity

The Banker's algorithm is used to determine if all requests for resources can be satisfied without leading to a deadlock. m is the total number of resources types n is the total number of processes NEED is an array of size m * n, it defines pending requests for each resources type. E.g.: NEEDi...

0
голосов
3ответов
3312 просмотров

Is it ever possible to have Big O less than O(1)?

Possible Duplicate: are there any O(1/n) algorithms? Is it ever possible for your code to be Big O less than O(1)?

16
голосов
11ответов
4980 просмотров

Do you use Big-O complexity evaluation in the 'real world'?

Recently in an interview I was asked several questions related to the Big-O of various algorithms that came up in the course of the technical questions. I don't think I did very well on this... In the ten years since I took programming courses where we were asked to calculate the Big-O of algori...

0
голосов
3ответов
1562 просмотров

Some Questions on Complexity

1) Reorder the following efficiency from smallest to largest: 2^n, n!, n^5, 10000, nlog2(n) My Ans-> 10000 Correct ? 2) Efficiency of an algo. is n^3, if a step in this algo. takes 1 nanosec. (10^-9 sec.). How long does it take the algo. to process an input of size 1000? I don'...

2
голосов
3ответов
3772 просмотров

how to find the time complexity using step count

sum(array,n) { tsum=0; for(i=0;i<n;i++) tsum=tsum+array[i]; return tsum; }

6
голосов
11ответов
3795 просмотров

Programming languages complexity

Is there an objective measure of a programming language's complexity in terms of syntax and semantics, not how complex the language is to use ? I've read many subjective comments but little rigorous analysis.

12
голосов
6ответов
14475 просмотров

Code complexity analysis tools beyond cyclomatic complexity

While cyclomatic complexity is a worthwhile metric, I tend to find it to be a poor tool for identifying difficult to maintain code. In particular, I tend to find it just highlights certain types of code (e.g. parsers) and misses difficult recursion, threading and coupling problems as well as man...

75
голосов
6ответов
108177 просмотров

Событие выхода из консольного приложения .NET

Есть ли в .NET метод, например событие, для определения выхода консольного приложения? Мне нужно очистить некоторые потоки и COM-объекты. Я запускаю цикл сообщений без формы из консольного приложения. Компонент DCOM, который я использую, похоже, требует, чтобы приложение перекачивало сообщени...