I want to get the power of an matrix. I mean lets say my matrix is A i
wanna get the A ^k.
I have though the simple algorithm that gives me O(n^3).I though I could do
some kind of a change to modify it and be faster. I could use the algorithm
that is used to get the power of a number that
consider code to find n^k where n is an integer
int power()
{
int ans=1,val=1;
while(k)
{
val=val*n;
if(k1)ans=ans*val;
k=k1;
}
return ans;
}
now if n is is a matrix all you have to do is replace * by matrix
multiplication algorithm
--
O(nlogn) algo
for each postion in paragraph store the frequency of the given words(from
start point to this point) .
now in resultant array you need to two indexes that have =1 value in the
difference of the frequency of two points.
eg hello hello are you
hello ,you
hello hello are you
1
Just to make sure I understood your code that if means that in case the k
is an odd number just multiply the accumulator 1 time with the val and
continue with even k.A question I have is if a recursive implementation
of this would be any faster?
Τη Σάββατο, 19 Ιανουαρίου 2013 1:06:25 μ.μ.
both recursive and iterative codes are O(nlogn) algos..
but memory will be more in recursion..
so we will prefer iteration
--
@Guneesh: I think you mean to say that the complexity of both the iterative
and recursive algorithms is O(n^3 log k), using the notation of the
original poster (A is n-by-n, and it is to be raised to the power k).
If what you really need is a way to calculate A^k * x, for some vector x,
it
@Guneesh: I don't think your code is correct. You want val to take on the
values n, n^2, n^4, n^8, ..., whereas in your code, val takes on the values
1,n, n^2, n^3, The algorithm should be more like this:
int power()
{
int ans=1,val=n;
while(k)
{
if(k1)ans=ans*val;
k=k1;
@dave thanks for correcting :)
--
Given a BST, how would you return the nth smallest element. The code had to
cover all the edge cases and was expected to write a logn solution.
--
Umer
--
I didn't understand your procedure.
For example
Given paragraph
This is a test. This is a programming test. This is a programming test
in any language.
Given words
this
a
test
programming
Output Shortest subsegment is
a programming test This
--
With love and regards,
Sairam Ravu
I
How does your algo give solution to this example?
--
With love and regards,
Sairam Ravu
I M.Tech(CS)
Sri Sathya Sai Institute of Higher Learning
To live life, you must think it, measure it, experiment with it,
dance it, paint it, draw it, and calculate it
--
11 matches
Mail list logo
