Tag Info

Hot answers tagged

28

When calculating the Big-O complexity of an algorithm, the thing being shown is the factor that gives the largest contribution to the increase in execution time if the number of elements that you run the algorithm over increases. If you have an algorithm with a complexity of (n^2 + n)/2 and you double the number of elements, then the constant 2 does not ...


10

Compare a linear to a binary search. Linear search has O(n) time complexity vs O(log n) for the binary search. For a large example, such as finding the definition of a word in a dictionary, the time difference will be enormous, and both algorithms can be easily carried out by hand.


9

The definition is that f(n) = O(g(n)) if there exists some constant C > 0 such that, for all n greater than some n_0, we have |f(n)| <= C * |g(n)| This is clearly true for f(n) = n^2 and g(n) = 1/2 n^2, where the constant C should be 2. It's also easy to see that it's true for f(n) = n^2 and g(n) = 1/2 (n^2 + n).


5

This isn't how ACO works. ACO only drops pheromones after ants have moved across all the points in the grid. You then evaluate something (perhaps total travel time) and then drop pheromones for good ants, and repeat. They don't move to the same vertex twice, generally, though you can customize this for implementation specificness. Pheromones aren't ...


5

You could do this with any string distance function. For example, consider the following distance function: distance(a, b) { return calc(a, b); } If you make the order of the arguments significant, then you can invert the sign of the result as needed: distance(a, b) { var first = getFirstAlphabetically({a, b}); var isNegative = (a != ...


4

Actually you should break the function down first: A loop has a few parts: the header, and processing before the loop. May declare some new variables the condition, when to stop the loop. the actual loop body. It changes some of the header's variables and/or the parameters passed in. the tail; what happens after the loop and return result. Or to write ...


4

When talking about complexity, you're only interested in the time factor changes based on the number of elements (n). As such you can remove any constant factor (like the 2 here). This leaves you with O(n^2 + n). Now, for a reasonable large n the product, i.e. n * n, will be significantly bigger than just n, which is the reason you're allowed to skip that ...


4

In this specific case, you can replace the variables with their minimum and maximum values to find the number of steps for each loop. The first loop goes from 0 to n, the second loop goes from 0 to n*n and the inner loop goes from 0 to n*n. So there are n2 iterations of the innermost loop, times n2 iterations of the second loop, times n iterations of the ...


3

It's not that "(n² + n)/2 behaves like n² when n is large", it's that (n² + n)/2 grows like n² as n increases. For example, as n increases from 1,000 to 1,000,000 (n² + n) / 2 increases from 500500 to 500000500000 (n²) / 2 increases from 500000 to 500000000000 (n²) increases from 1000000 to 1000000000000 Similarly, as n increases from ...


3

It just looks like you need to work out the big O notation a bit more. How convenient this notation is, it is very misleading because of the use of an equal sign, which is not used here to denote the equality of functions. As you know, this notation expresses an asymptotic comparisons of functions, and writing f = O(g) means that f(n) grows at most as fast ...


3

When you find a statement like "M number of comparisons" about sorting algorithms in literature, the author typically means the number of comparisons between the sorted elements, not the comparisons of something like loop indexes. So if you are asked this in a university assignment, I would guess that this is the number which is meant (but to make that ...


3

This brings back memories of an Operations Research class I had in college a very long time ago. You might want to do some googling on the Assignment problem and the Generalized Assignment problem for some background info and more rigorous solutions. Having said that, I'd do the following: Put all the entities that can be processed by the same set ...


2

Calculating fibonacci numbers. The obvious algorithm is to just implement its recursive mathematical definition as code, and that's O(phi^n). There's a linear algorithm using a straightforward for loop that's O(n), and a O(log n) algorithm that uses a formula for fib(2*n). You could let him sit at a REPL and calculate fib(n) for various n using ...


2

First, there is high possibility that combination of parameters and starting cards might be unsolvable. For example N=3; K=2 1 0 1 Is unsolvable. Your algorithm doesn't find minimum number of steps, because your example configuration cannot be solved at all. Now the question is whenever given algorithm does indeed guarantee that it can always find ...


2

1) about stack overflow - if your algorithm will stop, but graph is too large, use explicit stack (on heap) instead of recursion. One way (not the only way) to prove that it will stop someday, is that size of problem is reduced EACH "round" and that "round" itself is limited by some constant. 2) You didn't say how exactly should position of diamons be ...


2

One great resource: http://bigocheatsheet.com/ I can tell you right off the bat that: Bubble Sort is in worst case, O(N2) Insertion Sort is in worst case, O(N2) Selection Sort is in worst case, O(N2) Quick Sort is in worst case, O(N2), yet is typically O(n log n) Merge Sort is in worst case, O(n log n)


1

Yes, it's true. Both strings and decimals, as well as all other types, are represented in binary. However, the problem lies in the significance of the binary. You cannot simply read a string as a decimal, or at least you shouldn't if you were looking to get the decimal representation of that decimal. Take for example this string in ASCII: "1.5" In ...


1

We do work with binary representations of numbers internally, but ultimately people want to use a computer program, and there the format isn't usable. So we do need to have code for converting string representations of things into binary, but only for new data entered by the user. People are extremely bad at remembering information-dense representations - ...


1

Since you posted this on the programmers site, I assume you are interested in answering this question from a "How do I become a programmer that can solve this problem" prespective, and not a stack-overflow prespective. To solve problems like these here's some suggetsions: How do others solve it? (i.e siri, ask.com, chacha, etc.) What research is ...


1

if n was a 1,000,000 then (n^2 + n) / 2 = 500000500000 (5.00001E+11) (n^2) / 2 = 500000000000 (5E+11) (n^2) = 1000000000000 (1E+12) 1000000000000.00 what? While the complexity gives us a way to predict a real-world cost (seconds or bytes depending on whether we are talking about time complexity or space complexity), it doesn't ...


1

I think you misunderstand what the big O notation means. When you see O(N^2) it basically means: when the problem gets 10 times as large, the time to solve it will be : 10^2 = 100 times as large. Let's punch 1000 and 10000 in your equation: 1000: (1000^2 + 1000)/2 = 500500 10000: (10000^2 + 10000)/2 = 50005000 50005000/500500 = 99,91 So while the N got ...


1

What are some methods for pathfinding in a 3d world? The same as a 2D world. Most pathfinding algorithms work on graphs, and will happily work with an arbitrary number of paths from a node. You might have some challenges building that graph from your existing data structures; and you might need to change your distance/heuristic for how "good" a path ...


1

Overview This is one way to solve that problem. imagine a request. It contains information defining the request (is it an update of data, or is it a request for the current data), and way for the requester to be notified that the request has been actioned, and of its results. Next up, you have a queue. You place the request into the queue, and at some ...


1

You dont initialize k-means using Euclidean distance. There are a range of initialization methods. The most intuitive is selecting random instances from your data and initializing there. That way each cluster in your first assignment step has at least one instance. The assignment step is where you apply a distance measure, like euclidean distance.


1

There are two concerns. First is repeatability and predictability. This is usually only concern in security-critical applications. There, having HW randomness generator (like the Geiger counter) is highly valuable thing and greatly improves the security of algorithm that depends on the random values. Second concern are "statistical" properties of the ...


1

The usual pseudo-random sources on a PC are very bad in the sense that they can be predicted 100%. But it is important to remember that this makes them unsuitable only for tasks that depend on secrecy, e.g. cryptography with a private key. For that, predictable values are obviously bad. In practice, you're only protected against snooping by the fact that ...


1

This is originally a comment seeking clarifications, but is too long to fit. So I posted each question here, along with my "what-if" answers for each question based on possible responses. Before seeking clarifications, everyone should see that the current implementation has time complexity that is quadratic in the number of waypoints. The notation is ...


1

Dynamic programming is much better than brute force plus a few heuristics. Try to determine the minimum number of digits so that some 0-1 integer is a mod n. For example, you could make a dictionary whose keys will be integers mod n, and whose values are the least number of digits so that there is some 0-1 integer equal to the key mod n. Start with (0,0). ...


1

It is possible for each variable to be uniformly distributed on an interval while the joint distribution is satisfies a codimension 1 constraint. For example, if you pick (x,y,z) so that it is uniformly distributed on a unit sphere, then each coordinate is uniformly distributed on the interval [-1,1]. The coordinates are just not independent. Even if you ...


1

I'd use Integer Linear Programming (which, in essence, is constraint programming, which is what you are doing) to solve this kind of problem, using CPLEX in conjunction with Visual Studio. As stated in your post, the objective of your program will be to maximize a goal given a set of constraints (e.g. total budget must be less than $200,000). To get ...



Only top voted, non community-wiki answers of a minimum length are eligible