I want to know the time complixity in details for this code -
public class
-
{
-
-
for (int i = 0; i < limit; i++)
-
{
-
d = fun(i) ; // call to function
-
m=((i >> d) + 1) >> 1;
-
d3=2 - (num1+ d)%2;
-
s = (m*d3)%3;
-
int dest = (m + d3)%3;
-
cout<<d3<<d2
-
}
-
-
-
-
static int fun(int i)
-
{
-
int g, x = i+1;
-
for (g = 0; x%2 == 0; g++) x /= 2;
-
return g;
-
}
-
-
} // end of class
For the first average complexity of fun() is constant equals 2.
The second it too long, didn't read it but it's looks Towers of Hanoi problem and its complexity is explained e.g. in wikipedia article.
17 3510
and also the time complixity for this code pls - #include <iostream>
-
#include <stack>
-
-
using namespace std;
-
-
void output(int value, int from, int to)
-
{
-
char towerNames[3] = {'A', 'B', 'C'};
-
cout << "Move disc " << value << " from " << towerNames[from] << " to " << towerNames[to] << endl;
-
}
-
-
int main() {
-
int n = 0;
-
cout << "Enter number of discs: ";
-
cin >> n;
-
-
stack<int> temp;
-
stack<int> towers[3];
-
int recent = 0;
-
bool broke = false;
-
-
cout << "Tower A contains the following discs(from top to bottom): ";
-
for(int i = 0; i < n; i++) {
-
towers[0].push(n-i);
-
cout << (i+1) << " ";
-
}
-
cout << endl << endl;
-
-
bool isEven = false;
-
if((n % 2) == 0) isEven = true;
-
-
while((towers[1].size() < n) && (towers[2].size() < n)) {
-
for(int i = 0; i < 3; i++) {
-
if(!towers[i].empty()) {
-
if(towers[i].top() != recent) {
-
if(isEven) {
-
for(int j = 1; j < 3; j++) {
-
if(towers[(i+j)%3].empty()) {
-
towers[(i+j)%3].push(towers[i].top());
-
recent = towers[i].top();
-
output(towers[i].top(),i,(i+j)%3);
-
towers[i].pop();
-
broke = true;
-
break;
-
}
-
else if(towers[(i+j)%3].top() > towers[i].top()) {
-
towers[(i+j)%3].push(towers[i].top());
-
recent = towers[i].top();
-
output(towers[i].top(),i,(i+j)%3);
-
towers[i].pop();
-
broke = true;
-
break;
-
}
-
}
-
}
-
else {
-
for(int j = 2; j > -1; j--) {
-
if(towers[(i+j)%3].empty()) {
-
towers[(i+j)%3].push(towers[i].top());
-
recent = towers[i].top();
-
output(towers[i].top(),i,(i+j)%3);
-
towers[i].pop();
-
broke = true;
-
break;
-
}
-
else if(towers[(i+j)%3].top() > towers[i].top()) {
-
towers[(i+j)%3].push(towers[i].top());
-
recent = towers[i].top();
-
output(towers[i].top(),i,(i+j)%3);
-
towers[i].pop();
-
broke = true;
-
break;
-
}
-
}
-
}
-
-
}
-
}
-
if(broke) { broke = false; break; }
-
}
-
}
-
-
cout << endl << "Tower C now contains the following discs(from top to bottom): ";
-
while(!towers[2].empty()) {
-
cout << towers[2].top() << " ";
-
towers[2].pop();
-
}
-
-
return 0;
-
}
For the first average complexity of fun() is constant equals 2.
The second it too long, didn't read it but it's looks Towers of Hanoi problem and its complexity is explained e.g. in wikipedia article.
Also, using the code tag would help others read it and provide help.
okay , thank you for your help
If you can help me to calculate the 1est code complixity
Your first post asked for time complexity, but your most recent post asked for code complexity. Do you want ... - result of a static analysis of the program; akin to Cyclomatic Complexity?
- rough estimate of the execution time (computational complexity); akin to O(N^2)?
thankyou donbock but I mean time complexity ,
Please be a little more forthcoming.
How do you need to report time complexity? Personally, I am most familiar with Big-O notation; for example O(1), O(N), O(logN), O(NlogN), O(N^2), and so on. Is that what you want?
yes,Big-O notation , thankyou very much for your help
I've reprinted the code from your first post with a couple of changes. I'm only looking inside the public class braces because I don't do C++; I replaced the call to 'fun' by the contents of that function to simplify the analysis; and I replaced 'limit' with 'N' to match big-O notation. - for (int i = 0; i < N; i++)
-
{
-
int g;
-
for (g = 0,x=i+1; x%2 == 0; g++)
-
{
-
x /= 2;
-
}
-
d = g;
-
m=((i >> d) + 1) >> 1;
-
d3=2 - (num1+ d)%2;
-
s = (m*d3)%3;
-
int dest = (m + d3)%3;
-
cout<<d3<<d2
-
}
Big-O notation is primarily interested in counting loop interations. There are two loops. - The outer for-loop obviously executes N times.
- The inner loop is the tricky one. How many times do you think it executes for each value of i+1?
You need to participate in finding the solution.
okay let me think , if we can write the i+1 as 2^n , so we will execute the iner loop n times , I mean when i=3 -> i+1=4 ->2^2 , so we will execute the innner loop 2 times , otherwise if the number is dividable by 2 but we cant write it as 2^n we will execute it 1 times ,
@bona3
What about, for example, i+1=24. This isn't a power-of-two, but the loop will execute more than once.
Hint: look at the binary representation of the various values of i+1.
mmmmmmmmmm your greate , the inner loop will execute to (number of zero ) times , I mean 2 =10 -> 1 time , 8=1000->3 times
Now you need to calculate the average number of iterations of the inner loop for numbers from 1 to N.
@bona3
That is, the number of loop iterations is equal to the number of trailing zeroes. For example, 20 (binary 10100) will have two iterations.
okay lets complete the solution coz I have to submit the home work tomorrow
@bona3
Then you had better follow newb16's advice. You can either do that analytically (solve the numerical sequence) or empirically (list values of i+1 from 1 to something manageable, put the number of iterations in the next column, put the average value of the first row to the current row in the next column, and try to recognize a pattern).
I will point out that the number of trailing zeroes has to be less than the number of bits; and the number of bits is O(logN). Adding in the effect of the outer loop we find that the time complexity of your function is less than O(NlogN). But don't settle for this approximate answer ... spend a little time working as outlined above and you should get the right answer.
thankyou very much for both of you
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Cliff Wells |
last post by:
Hi,
I'm writing an application that needs to know if an Internet connection
is available. Basically, I want to have something similar to what a lot
of email clients have, where the app can work...
|
by: Edg Bamyasi |
last post by:
This Is A Late Cross Post from comp.lang.python. It seems the mistery
is deeper then i expected.
What is the running time of conactination on character strings.
i.e.
>> joe="123"
>>...
|
by: Luca |
last post by:
I have the following problem:
I'm developing a system where there are some processes that
communicate each other via message queues; the message one process can
send to another process is as...
|
by: HateSpam |
last post by:
I am trying to write a function that determines how many hours there are
until a certain date/time that depends on what today's date/time is.
Basically, how many hours from now until the next...
|
by: davide.sammartino |
last post by:
Hi,
when the processor meet this instruction
i >4;
the operation, inside the processor, is computed constantly or linearly
in time?
|
by: Lionel B |
last post by:
Hi,
Anyone know if the Standard has anything to say about the time complexity
of size() for std::set?
I need to access a set's size (/not/ to know if it is empty!) heavily
during an algorithm...
|
by: Jens |
last post by:
Posted to:
comp.periphs.printers
comp.lang.c
comp.lang.postscript
Hello,
I am looking for some publically available methods/algorithms or C source
code for detecting
|
by: desktop |
last post by:
In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q is
a pointer to an element can be done in amortized constant time.
I guess that is not worst case since std::set is...
|
by: youtoo |
last post by:
It has been extensively discussed the time complexity (quadratic) of
string concatenation (due to string's immutability).
But what is:
== the time complexity of string indexing? Is it constant?...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
| |