# Tag Info

266

There is no necessary relation between the implementation of the compiler and the output of the compiler. You could write a compiler in a language like Python or Ruby, whose most common implementations are very slow, and that compiler could output highly optimized machine code capable of outperforming C. The compiler itself would take a long time to run, ...

98

How can a machine built by a man be stronger than a man? This is exactly the same question. The answer is that the output of the compiler depends on the algorithms implemented by that compiler, not on the langauge used to implement it. You could write a really slow, inefficient compiler that produces very efficient code. There's nothing special about a ...

90

I want to make one point against a common assumption which is, in my opinion, fallacious to the point of being harmful when choosing tools for a job. There is no such thing as a slow or fast language.¹ On our way to the CPU actually doing something, there are many steps². At least one programmer with certain skillsets. The (formal) language they program ...

54

There are a number of well-studied strategies; which is best in your application depends on circumstance. Improve worst case runtime Using problem-specific insight, you can often improve the naive algorithm. For instance, there are $O(c^n)$ algorithms for Vertex Cover with $c < 1.3$ [1]; this is a huge improvement over the naive $\Omega(2^n)$ and might ...

40

The best algorithm that is known is to express the factorial as a product of prime powers. One can quickly determine the primes as well as the right power for each prime using a sieve approach. Computing each power can be done efficiently using repeated squaring, and then the factors are multiplied together. This was described by Peter B. Borwein, On the ...

36

On the contrary. At the same time that hardware is getting cheaper, several other developments take place. First, the amount of data to be processed is growing exponentially. This has led to the study of quasilinear time algorithms, and the area of big data. Think for example about search engines - they have to handle large volumes of queries, process large ...

32

Another perspective on "efficiency" is that polynomial time allows us to define a notion of "efficiency" that doesn't depend on machine models. Specifically, there's a variant of the Church-Turing thesis called the "effective Church-Turing Thesis" that says that any problem that runs in polynomial time on on kind of machine model will also run in polynomial ...

32

All complexities you provided are true, however they are given in Big O notation, so all additive values and constants are omitted. To answer your question we need to focus on a detailed analysis of those two algorithms. This analysis can be done by hand, or found in many books. I'll use results from Knuth's Art of Computer Programming. Average number of ...

31

I really like the example from Introduction to Algorithms book, which illustrates significance of algorithm efficiency: Let's compare two sorting algorithms: insertion sort and merge sort. Their complexity is $O(n^2) = c_1n^2$ and $O(n\log n) = c_2n \lg n$ respectively. Typically merge sort has a bigger constant factor, so let's assume $c_1 < c_2$. To ...

30

I see four main ways to solve this problem, with different running times: $O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time. $O(n \: log \: n)$ solution: sort the arrays beforehand; then, perform a ...

29

The confusion arises from difference between the conceptual description of the algorithm, and its implementation. Logically merge sort is described as splitting up the array into smaller arrays, and then merging them back together. However, "splitting the array" doesn't imply "creating an entirely new array in memory", or anything like that - it could be ...

25

We count the number of array element reads and writes. To do bubble sort, you need $1 + 4n$ accesses (the initial write to the end, then, in the worst case, two reads and two writes to do $n$ swaps). To do the binary search, we need $2\log n + 2n + 1$ ($2\log n$ for binary search, then, in the worst case, $2n$ to shift the array elements to the right, then 1 ...

23

Quick answer: Never, for practical purposes. It is not currently of any practical use. First, let's separate out "practical" compositeness testing from primality proofs. The former is good enough for almost all purposes, though there are different levels of testing people feel is adequate. For numbers under 2^64, no more than 7 Miller-Rabin tests, or ...

23

There is one forgotten thing about optimisation here. There was longish debate about fortran outperforming C. Putting apart malformed debate: the same code was written in C and fortran (as testers thought) and performance was tested based on same data. The problem is, these languages differ, C allows pointers aliasing, while fortran does not. So the codes ...

18

What you are looking for is "approximate near neighbor search" (ANNS) in the Levenshtein/edit distance. From a theoretical perspective, edit distance has so far turned out to be relatively hard for near-neighbor searches, afaik. Still, there are many results, see the references in this Ostrovsky and Rabani paper. If you are willing to consider alternative ...

18

Keep in mind that the factorial function grows so fast that you'll need arbitrary-sized integers to get any benefit of more efficient techniques than the naive approach. The factorial of 21 is already too big to fit in a 64-bit unsigned long long int. As far as I know, there is no algorithm to compute $n!$ (factorial of $n$) which is faster than doing the ...

18

The (asymptotically) most efficient deterministic primality testing algorithm is due to Lenstra and Pomerance, running in time $\tilde{O}(\log^6 n)$. If you believe the Extended Riemann Hypothesis, then Miller's algorithm runs in time $\tilde{O}(\log^4 n)$. There are many other deterministic primality testing algorithms, for example Miller's paper has an $\... 18 Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size$N$with high probability by querying the database only$O(\sqrt{N})$times. Any classical solution that succeeds with high probability requires$\Omega (N)$queries to the database. 17 The problem you are asking for is a well-known algorithmic problems. It is actually still open, how hard this problem exactly is. Also you should know that there are different incarnations of this problem. In contrast what you are asking for, usually only the distances are returned, whereas you are asking for the the actual shortest paths. Notice that these ... 16 The$\Theta(n)$difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation$\oplus$that is: total, such that for any values$a$and$b$,$a \oplus b$is defined and of the same type (or at least of some appropriate supertype of it, for which the ... 15 Regular language membership can be decided in$\cal{O}(n)$time by simulating the language's (minimal) DFA (which has been precomputed). Context free language membership can be decided in$\cal{O}(n^3)$by the CYK Algorithm. There are decidable languages that are not in$\sf{P}$, such as those in$\sf{EXPTIME}\setminus \sf{P}$. 15 There are two answers, depending on how you define efficient. Compactness of representation Telling more with less: NFAs are more efficient. Converting a DFA to an NFA is straightforward and does not increase the size of the representation. However, there are regular languages for which the smallest DFA is exponentially bigger than the smallest NFA. A ... 14 The different dimensions are independent. What you can do is compute, for each dimension j, how many different walks there are in just that dimension which take$t$steps. Let us call that number$W(j,t)$. From your question, you already know how to compute these numbers with dynamic programming. Now, it's easy to count the number of walks that take$t_i$... 14 The problem as you probably have noticed is a quite difficult problem. Checking the web will lead to some complex instances that probably you will not need. Here is a solution - as required (i.e. you dont need to recalculate everything from scratch). for the case of adding an edge$(u,v)\$ - then using your already built-distance matrix - do the following : ...

14

Element = Sum(Array2) - Sum(Array1) I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps. If the number of added elements is more than one, this won't work. My answer has the same run time complexity for best, worst, and average case, EDIT After some thinking, ...

14

I'd post this as a comment on Tobi's answer, but I don't have the reputation yet. As an alternative to calculating the sum of each list (especially if they are large lists or contain very large numbers that might overflow your data type when summed) you can use xor instead. Just calculate the xor-sum (i.e. x[0]^x[1]^x[2]...x[n]) of each list and then xor ...

12

Other answers have addressed this from a more theoretical perspective. Here is a more practical approach. For "typical" NP-complete decision problems ("does there exist a thingy that satisfies all these constraints?"), this is what I would always try first: Write a simple program that encodes your problem instance as a SAT instance. Then take a good SAT ...

12

The data structures you are interested in are metric trees. That is, they support efficient searches in metric spaces. A metric space is formed by a set of objects and a distance function defined among them satisfying the triangle inequality. The goal is then, given a set of objects and a query element, to retrieve those objects close enough to the query. ...

12

The knowledge of algorithms is much more than how to write fast algorithms. It also gives you problem solving methods (e.g. divide and conquer, dynamic programming, greedy, reduction, linear programming, etc) that you can then apply when approaching a new and challenging problem. Having a suitable approach usually leads to codes which are simpler and much ...

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