Hi Jason, I took Intro to Programming at Albright College and we used Starting Out with Python 3rd ed. Right now I am taking Data Structure and Analysis and we are using This book : http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html
Thanks Alan for your explanation. The problem with me getting these terms and things is in part due to the accelerated rate in which my classes run. I cant possible master anything in a 6-8 week course, especially when I have zero programming background and about 2/3 of the class does... So I'll fake it till I make it. Thanks a lot. I think I have a very basic understanding of Big O right now. But if someone could please make it a little easier to figure out postfix and infix? My homework assignment asks me to convert from infix to postfix. I got a very very basic understanding of this but when the problems get a little more involved I get totally lost. Here is an example A+B/C*D-E+F I thought it was something like ABC/+ cd*ef+-?? That's probably wrong but I am trying Stephanie Quiles Sent from my iPhone > On Jul 28, 2015, at 10:07 AM, Joseph Lee <joseph.lee22...@gmail.com> wrote: > > Hi Stephanie, > I'm wondering which courses you were introduced to Python and which book you > are using. I do understand how it might be difficult to understand this > concept, especially for someone who is a complete novice to algorithm > analysis where Big O shows up. > I'll answer you inline. > > -----Original Message----- > From: Tutor [mailto:tutor-bounces+joseph.lee22590=gmail....@python.org] On > Behalf Of Quiles, Stephanie > Sent: Monday, July 27, 2015 6:30 PM > To: python tutor <tutor@python.org> > Subject: [Tutor] the big o > >> Hello, > >> I am trying to figure this out but i do not understand any of it. the > question asks give the big-o performance of the following code fragment: > >> for i in range(n): >> for j in range(n): >> k = 2 + 2 > >> I am not sure how i am supposed to figure this out. i have been reading > the book, looking at blog posts and watching online tutorials and i still > cannot grasp the > big-o. please keep in mind that i have never taken a calc > course and that i am a complete novice to programming, even more so to > python. Any help would be greatly appreciated. I am pretty much on my own > with these since my fellow students are unwilling to help me with anything > since they are far more advanced than i am. > >> Thank you, > >> Stephanie > > JL: Okay, let's start from the very beginning. First, before talking about > what Big O means, it is important to go over some basics: > > Big O comes from algorithm analysis, a branch of computer science dealing > with coming up with solutions to problems and analyzing them. In our > context, an algorithm is a list of precise steps to solve a problem. For > example, using Alan's searching example, it could be paraphrased as follows: > > Suppose I have a list of items and I want to search for a specific item. How > would I do this? > > If your friend was asked to do this, what would he or she do? Obviously, > your friend will search for items one at a time until what you are looking > for is found. You or your friend could say: > > First, have a list of items. Then examine one item at a time until what I > want is found. > > This is a description of an algorithm: precise steps to be followed. The > above paragraph describes searching algorithms - given a list of items, a > computer (or a machine whether it's physical or virtual) will go through the > list and compare each item to the target it is looking for. There are more > elegant ways of doing it that mimics how humans perform specific searches, > including the one that Alan described (called logarithmic search, commonly > introduced as binary search in earlier courses). > > Once you have an algorithm, it is time to think about how to implement, or > write it in Python. This is where you need to become skilled at translating > paper instructions to something that Python can understand. In case of > Alan's linear search example, one way to put it is: > > For item in items: > if item == target: > position = items.index(item) > return position > > Essentially, this code fragment says to perform a linear search on a list of > items. As part of learning about Big O and algorithms, it is important to > practice how to translate between English and Python: translate a > description of an algorithm in English to Python by implementing it, and > understand what the code fragment does. > > Now the topic at hand: For decades, computer scientists and software > developers were asking themselves, "how can we make our programs run faster > and use fewer resources?" This is where Big O comes into play: Many computer > science textbooks define Big O as worst--case running time of algorithms. > That is, Big O describes how an algorithm will behave when it encounters > input that'll cause it to run slowest. In a nutshell, an algorithm (or a > program) will take in a set of values (called input), do something with it > (searching, sorting, send and receive data between computers, etc.) and > return one or more results (output). > > Many people would want to assume that algorithms will work on typical data > only. In reality, algorithms can encounter input that it may have hard time > to process. For example, if a program is asked to sort a list, it will > expect to get a list of items that can be sorted using fewest resources and > can be done quickly. There is one kind of input that this program will have > hard time with (I'll let you figure out what this input might be; may I ask > that we let Stephanie figure this out? That way she can understand how > algorithm design works). > > Now you know what the worst possible input to an algorithm is like, you are > ready to tackle the actual definition of Big O. Simply put, Big O is running > time of an algorithm given a worst-case input. This is way different from > what the book asks: the question and the accompanying code fragment simply > asks for running time, not exactly Big O, hence the reason I asked which > course you are taking and book that's used (Big O is reserved for computer > science courses dealing with algorithms). Based on our discussion so far, > there must be one more thing involved when talking about Big O: input data, > and I'm leaning towards shaking my head at this point, seeing that the > question could confuse novices (it is way too early to be introduced to Big > O unless if you are taking a course in algorithms). > > In case of the code fragment above, as I said in a previous message, the > easiest way to calculate Big O is to look at what the inner loop does. Once > you understand that, look at the outer loop. I think the easiest way to look > at this is through a real-life example: suppose you have a bunch of boxes > full of books, and you want to find a specific book. You would open each box > and look through various books, looking for the book you need. If you didn't > find the book you are looking for, you'd move onto the next box, right? > That's exactly what's going on here: > > * The inner loop: you look for books in one box. > * Outer loop: you repeat this search for all boxes. > > And the result you get is the running time of this algorithm. It turns out > there are more elegant ways to do this given the right input, and this > algorithm or a variation is invoked in many real-life situations such as > searching for a character in strings, searching for files in folders, > sorting and so on (hint: the running time of this algorithm is not > logarithmic; there are logarithmic (chopping) algorithms that has polynomial > Big O value, with a well-known example being quicksort (you tell the > algorithm to define a pivot that'll be used to align items for ease of > sorting) which has Big O or worst-case running time of N squared). > > Hope this helps. Good luck in your courses. > Cheers, > Joseph > _______________________________________________ > Tutor maillist - Tutor@python.org > To unsubscribe or change subscription options: > https://mail.python.org/mailman/listinfo/tutor > _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
