|
How can i calculate time complexity and space complexity?
|
|
|
|
|
Calculating time complexity for an algorithm means getting an estimate of the number of cycles it must undergo in order to solve the problem.
As a very simple example, a dumb search algorithm on a vector of size n will have time complexity O(n), since it will go through all the vector's cells to find the key - the "big O" indicates the order of time complexity, and is the standard way of writing time complexity.
On the other hand, a binary search will have time complexity O(log2 n), since it will divide the vector in two at each cycle.
Calculating all permutations of a given set of items has time complexity O(n!) (NP-Complete class of time complexity), and so on.
The same goes for calculating space complexity (EDIT: what I mean is if you use for example only a vector of length n, then the space complexity is n, and so on.).
Have a look here[^] for more info.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
modified on Friday, August 14, 2009 2:18 PM
|
|
|
|
|
i need more explanation
how can we calculate o(n), o(n2),o(nlogn)
if i have one problem, hoe can i calculate like that
and also space complexity
|
|
|
|
|
I need some guides from you.
I want to know whether HMM or Markov model is the right choice for target tracking.
I want to choose a method or an algorithm using vc++ to realize target tracking.
Or which method is good for doing this project?
|
|
|
|
|
For tracking try googling phrases such as:
1. particle filter
2. mean-shift
|
|
|
|
|
Thank you for your care. I have found out that there are many articles concerned about particle filter and mean-shift.
But I wanna figure out whether I can use Markov or HMM to finish this project.
It seems that there are only a few papers which use these stochastic method.
|
|
|
|
|
superwave wrote: It seems that there are only a few papers which use these stochastic method.
Funny, I did a pretty restrictive Google search and got over 1400.
Google It[^]
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Thank you for your help.
modified on Monday, August 10, 2009 12:40 AM
|
|
|
|
|
Dear Sir/Madam,
Me Rakesh Ranjan Dey,Software Engineer,working at software company and also doing M Tech in Computer Sc. & Eng.I have to do a project named structured data extraction that wiil extract data from web and put into database.I have to create a DOM tree for a particular web page.So I am requesting you to guide me about how to create DOM tree with some useful code to extract structured data extraction from web so that I will be thankful to you.
Rakesh Ranjan Dey
|
|
|
|
|
|
Hi people, i am doing some 'while' loop but kinda stuck somewhere.
What i want to do is actually is comparing from 2 database tables.
The problem now is example i have 10 records in SMS_IN table, but my code only runs the first record everytime i calls it. By right, it should loop thru all the data and check.
SMS_IN (sample data)
originator | text | date
88411254 | Internet bla bla bla | 5 August
78412447 | Quiz ans1 ans2 ans3 | 5 August
USERAPP (sample data)
userid | keyword
54 | Internet
80 | Quiz
So the logic is first it will check the SMS_IN text column, example the first word of the first result is 'Internet', then it will check the USERAPP keyword column, if the keyword 'Internet' exists, means its a valid sms. If the keyword does not exists at all in the USERAPP table, the msg will be deleted from SMS_IN table
this is my code
ResultSet rs = null;
ResultSet rs2 = null;
String sql = "Select * from smsserver_in";
String sql1 = "Select * from USERAPP";
rs = db.SelectDB(sql);
rs2 = db.SelectDB(sql1);
try {
String firstword = null;
String keyword = null;
int number = 0;
while (rs.next()) {
StringTokenizer st = new StringTokenizer(rs.getString("text"));
firstword = st.nextToken();
number = rs.getInt("id");
while (rs2.next()) {
keyword = rs2.getString("keyword");
if (firstword.equals(keyword)) {
out.println(number);
String sql3 = "Insert into app_" + keyword + "(originator,text)values(" + rs.getString("originator") + ",'" + rs.getString("text") + "')";
db.InsertDB(sql3);
String sql4 = "delete from smsserver_in where id=" + number;
db.UpdateDB(sql4);
} else {
}
}
}
} catch (Exception ex) {
}
}
|
|
|
|
|
Hi,
your code is wrong, it has two nested loops but acts as if there were only one loop.
Here is a very simple snippet with the same problem, it should help you in understanding what goes wrong:
int i1=0;
int i2=0;
for (; i1<10; i1++) {
for (; i2<10; i2++) {
Console.WriteLine("i1="+i1+" i2="+i2);
}
}
Now imagine you executing this code by hand.
If you still don't see it, run the code. Then use the debugger, set a breakpoint, and learn.
If you discover this, chances are you won't make the same mistake ever again.
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
|
|
|
|
|
Okay, anyway my loop is working already, but just some problems.
At which part should i add the code to delete the message after checking thru all the keywords and it does not match?
I tried adding a else statement inside the if statement of my inner loop but its not working
ResultSet rs = null;
ResultSet rs2 = null;
try {
String firstword = null;
String keyword = null;
int number = 0;
String sql = "Select * from smsserver_in";
rs = db.SelectDB(sql);
while (rs.next()) {
StringTokenizer st = new StringTokenizer(rs.getString("text"));
firstword = st.nextToken();
number = rs.getInt("id");
String sql1 = "Select * from USERAPP";
rs2 = db.SelectDB(sql1);
while (rs2.next()) {
keyword = rs2.getString("keyword");
if (firstword.equals(keyword)) {
out.println(number);
String sql3 = "Insert into app_" + keyword + "(originator,text)values(" + rs.getString("originator") + ",'" + rs.getString("text") + "')";
db.InsertDB(sql3);
String sql4 = "delete from smsserver_in where id=" + number;
db.UpdateDB(sql4);
}
}
}
} catch (Exception ex) {
}
modified on Tuesday, August 4, 2009 11:37 PM
|
|
|
|
|
As you want to delete a message when the keyword is not recognized, the logic is:
- get keyword from message
- compare with ALL valid keywords
- after comparison loop: if not found, delete message
hence you need a boolean "found" flag.
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
|
|
|
|
|
I've just begun studying parsing and lexical analysis, and I find it fascinating.
I wonder if parsing algorithms could be used to make a computer understand, say, the rules of a game, or the design of a spacecraft.
In other words, if we can represent concepts by tokens that a parser can understand, is it possible to use parsing technology for broader things than just compilers?
|
|
|
|
|
Richard Andrew x64 wrote: by tokens that a parser can understand
IMO a computer does not understand tokens, all it does is execute the rules you make up for it to identify tokens.
And yes, lexers and parsers can be used by more than compilers; their goal may be to calculate something (interpreters), to draw something (graphing calculators), to proof something (math theory building), etc.
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
modified on Tuesday, August 4, 2009 12:24 PM
|
|
|
|
|
Completely agree with Luc.
Richard Andrew x64 wrote: is it possible to use parsing technology for broader things than just compilers?
Aren't parser technologies used for other jobs than compiler designs?
Richard Andrew x64 wrote: I've just begun studying parsing and lexical analysis, and I find it fascinating.
It is all fascinating stuff. But it takes a long time and effort to come up with a decent working parser. I am working on an open source parser to parse Malayalam[^] language text and do grammar checking and it is taking long time than I expected.
|
|
|
|
|
I would have replied earlier but I didn't have a good example, but now I came across one. Scientific chemical names. They need to be parsed (since their structure is non-trivial), but that can't be called compiling
|
|
|
|
|
|
Richard Andrew x64 wrote: I wonder if parsing algorithms could be used to make a computer understand, say, the rules of a game, or the design of a spacecraft.
Yes and no. There is always ambiguity in language. One needs to be able to reason before you can "understand" a text. We (as humans) deduce meanings, interpret a text, or even skip words. It get's worse if the text contains things like sarcasm, pictures or figure of speech.
Richard Andrew x64 wrote: In other words, if we can represent concepts by tokens that a parser can understand, is it possible to use parsing technology for broader things than just compilers?
Sounds like Protege[^]
Parsing a text is one thing. Reasoning about it's content is a step up. Understanding a (short) text[^] - is even more difficult.
The computer is mightier than the pen, the sword, and usually the programmer.
|
|
|
|
|
I have trouble with the concept of a "production" in BNF.
Take, for instance, the following BNF snippet:
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Proper BNF terminology calls the things on the RIGHT side of the :=
"productions."
However, since the thing on the left of the := is made up of the things on the right, doesn't it make more sense to call the D the production?
|
|
|
|
|
would it help to call "D" the product, i.e. the result of the production?
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
|
|
|
|
|
That might help, but that nomenclature does not appear in the literature.
It just seems like such a backwards use of the word. And when words are used in alternative ways like that, it interferes with my understanding of the material.
|
|
|
|
|
Hi,
let me try again.
IIRC the righthand side is called a "production rule", not a "production".
Does that make more sense?
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
|
|
|
|
|
Oh, well, yes, that does make more sense.
I guess the paper I have been reading used a lazy abbreviation of the proper term.
That sheds a whole new light on things. Thanks.
|
|
|
|