https://i.imgur.com/Nj6H2VX.jpg
https://i.imgur.com/G9oe7S9.jpg
這題的(c)小題
不知道我這樣判斷時間複雜度行不行
麻煩各位
感恩

https://imgur.com/YepKQaE.jpglittle-o是big-o的子集，是小o一定是大O

懂了，原來同取log後要分得出絕對大小才能決定原來函數，之前沒特別注意過這種情況，感謝提醒

https://i.imgur.com/vrcZmRt.jpg那這個定理1-3和(c)小題是一樣的東西嗎，不管bigoh或是littleoh都成立?

對啊,一樣的，根據定義little oh成立則big oh就成立就是說f(n)=o(g(n))則f(n)=O(g(n))

https://imgur.com/a/w6UF1G1 根據林立宇老師演算法講義1-8的第一個定理 只有在little o的情況下這個定理才會成立如果這個定理改成big oh是不一定會成立的，反例很好找，例如n^2跟n^3

為什麼kloga>c比不出來常常兩邊取log是可以的但這題看得出指數比多項式大

我的想法是把c看成常數乘常數，klogn是常數乘對數，所以klogn會大於c，不知道這樣正不正確

nO多項式aO指數等級就不一樣了是我我就直接這樣判斷c就算給道1000還是贏不了a給1更正n^ca^n

kloga>c那句有問題吧，像樓上說的常數要取多少都可以，但n很大的時候等級比較大的還是會比較大

是可以這樣取log比，但是取log後要看little oh ，但是你寫<=有Big oh的感覺https://imgur.com/a/LxNwjIB

一般像logn^logn跟2^n這種才會去同取log比(c)小題同取log比也對，在論等級的時候常數係數都可以直接忽略，但這題一個指數一個多項式，層級就不一樣了一般直接判斷就好了想問na大為什麼同取log之後是little-o，好像沒特別注意過這邊的little big要怎麼取