c++ - Time complexity of enumerator - 


enum class color {     blue,     red,     green,     purple,     first=blue,     last=purple };  color operator++( color& x ) { return x = (color)(((int)(x) + 1)); }  color operator*(color c) {return c;}  color begin(color r) {return color::first;} // end iterator needs return 1 past end! color end(color r)   {return color(int(color::last) + 1);}   int main() {     (const auto& color : color()) std::cout << int(color); //0123     return 0; }

i have taken piece of code link.

i asked time complexity of similar piece of code. per understanding, o(n) enumerator element being iterated.
right answer on platforms says o(1) without explanation.
can confirm, o(1) , why?

when preform asymptotic complexity analysis, it's important define input size is. because that's complexity defined in terms of. analysis meaningful in way.

if instance algorithm defined have no input, can argue number of enumerators fixed , last - first. such loop body executed fixed amount of times, , o(1) it.

i can guess "some platform" part may refer ability of compilers optimize. when compiler sees loop preformed 4 times, may choose unroll it, instead of emitting code actual loop.

having said that, optimizations don't affect asymptotic complexity of algorithms. may @ affect coefficient hidden behind big-oh notation. loop o(1) either way, according analysis did above, coefficient smaller after unrolling optimization, since code pertains looping possibly gone.


Comments

Post a Comment

Popular posts from this blog

python - Operations inside variables -

this question has answer here: evaluating mathematical expression in string 12 answers i want make python script finds maximum possible output using 2 operations. problem says there syntax error @ 2nd last line, in b in there. how can fix it? x = 0 = int(input("1st number:")) c = int(input("2nd number:" )) e = int(input("3rd number:" )) in range(4): if == 0: b = "+" elif == 1: b = "-" elif == 2: b = "/" else: b = "*" j in range(4): if j == 0: d = "+" elif j == 1: d = "-" elif j == 2: d = "/" else: d = "*" k = b c d e print(k) if you're after variables e on single line, couldn...
Read more

Generic Map Parameter java -

i having lot of methods of type: public static list<eduusers> getdetails(class c, map<string, integer> params) { list<eduusers> details = null; session session = hibernateutil.getsessionfactory().opensession(); transaction tx = null; try { tx = session.begintransaction(); criteria cr = session.createcriteria(c); (map.entry<string, integer> entry : params.entryset()) { cr.add(restrictions.eq(entry.getkey(), entry.getvalue())); } details = cr.list(); tx.commit(); } catch (exception asd) { log.debug(asd.getmessage()); if (tx != null) { tx.commit(); } } { session.close(); } return details; } i trying have generic method them , have written far: public static <t> list<t> getdetails(class<t> c, class<t> b) { l...
Read more

arrays - What causes a java.lang.ArrayIndexOutOfBoundsException and how do I prevent it? -

what arrayindexoutofboundsexception mean , how rid of it? here code sample triggers exception: string[] name = {"tom", "dick", "harry"}; for(int = 0; i<=name.length; i++) { system.out.print(name[i] +'\n'); } your first port of call should documentation explains reasonably clearly: thrown indicate array has been accessed illegal index. index either negative or greater or equal size of array. so example: int[] array = new int[5]; int boom = array[10]; // throws exception as how avoid it... um, don't that. careful array indexes. one problem people run thinking arrays 1-indexed, e.g. int[] array = new int[5]; // ... populate array here ... (int index = 1; index <= array.length; index++) { system.out.println(array[index]); } that miss out first element (index 0) , throw exception when index 5. valid indexes here 0-4 inclusive. correct, idiomatic for statement here be: for (int index = 0; index <...
Read more