Yes Christiania/Kristiania = Oslo. My advice is NEVER consider a spelling to be definite or "correct".
I also searched through the databases of emigrants leaving from that port city and did not find your Albert.... in the 1870s which matched your information at all. There were of course many many Oles and Annas... too many. You will find the emigrant databases within the Digitalarkivet website.
You could also search through the church records of births/baptisms in the various congregations of Oslo at the time of Albert's birth or shortly thereafter. As Oslo was a fairly large city there were a number of different church congregations and their church records were kept in separate books. Those books are not indexed and you have to go through them page by page but scanning down a page of births/baptisms for the rather unusual name of Albert in the appropriate column of the page should be fairly straightforward for you.
The detail available in the extensive parish church records is a marvelous gift from Norway. The Digitalarkivet web site has been adding scanned images of the original Norwegian parish church records for anyone with Internet access since November 2005. To be able to use the parish records you must first know WHERE in Norway you want to search for this documentation.
The Digitalarkivet web site - (http://digitalarkivet.uib.no/cgi-win/WebFront.exe?slag=vis&a...
An English option is available by clicking on that word from either the left hand column or the blue link bar along the bottom of the homepage.
The scanned images are available from the homepage link "Skanna kyrkjebøker" [Norwegian version]/"Digitised parish records" [English version] which is listed along the left hand column and from the blue banner of links along the top section of the homepage.
When you click on that link another page will present a short list of choices - choose "Read the digitized parish registers"[English version]/"Lesa skanna kykrebøker" [Norwegian version].
After you've clicked on that link and a new main page has presented on the screen be sure and read the instructions that are available from the Digitalarkivet for navigating the scanned records. The instructions are available in Bokmål (official Norwegian), Nyorsk (Norwegian), Davvisámegiella (Saami), and English.
Recommended basic reading are the "Startsiden" [Norwegian version]/"Main page" [English version], "Brukerveiledning" [Norwegian version]/"User's guide" [English version] and "Om tjenesten" [Norwegian version]/"About this service" [English version].
Good information about translating the formats of Norwegian parish church records during various time periods, many of the basic terms used and understanding how to use the information should be studied at this web site -
For the protection of privacy, there are limits for how recent records can be:
- Birth and baptism records up to and including 1929
- Confirmation records up to and including 1934
- Marriage and banns records - no limits
- Civil marriage up to and including 1950
- Death, burial and stillbirth records up to and including 1930
- Migration records - no limits
- Joins and leavings of the State Church up to and including 1950
- Records about dissenters up to and including 1950
If you cross these limits while browsing a register or a list, you will not see the digitised image, but a message informing you that the image cannot be displayed.